Longest Substring Without Repeating Characters

Question: Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

You may view the full question here.

Approach 1: A simple strategy to maintain a HashMap to keep track of the characters that have already been encountered and the index location where it was last encountered.

The Map manipulations are quite expensive, and ours is a case where map manipulations occur almost as frequently as the look ups.

Although not the best solution, let’s explore this option for today.

//Approach 1
//Runtime: 8ms
//Memory usage: 38.8MB
class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        int start = 0, end = 0;
        int size = s.length();
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0, subLen = 0;
        while(end<size){
            if(!map.containsKey(chars[end]) || map.get(chars[end])<start){
                subLen++;
                map.put(chars[end], end);
                end++;
                max = Math.max(max, subLen);
            } else {
                start = map.get(chars[end]) + 1;
                subLen = end - start;
            }
        }
        return max;
    }
}

Find more posts here.

Cheers & Chao!