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.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Problem Clarification

We need to find the longest contiguous stretch that have all different characters. In other words, if such a contiguous stretch has length n, then there are n different characters.

Idea – 1

Try each of the substring and see if it has all different characters. Time and space .

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if(n == 0)
        {
            return 0;
        }
        
        int max = 1;
        for(int len = n; len > 1; --len)
        {
            int i = 0;
            while(i+len <= n)
            {
                int j = i+len-1;
                if(allDistinct(s, i, j))
                {
                    return len;
                }
                
                ++i;
            }
        }
        
        return max;
    }
    
    private boolean allDistinct(String s, int begin, int end)
    {
        HashSet<Character> seen = new HashSet<>();
        for(int i = begin; i <= end; ++i)
        {
            seen.add(s.charAt(i));
            if(seen.size() < i-begin+1)
            {
                return false;
            }
        }
        
        return true;
    }
}


Time limit exceeded for an input of length 31,000.

Idea - 2

Say we have a window [i, j] of contiguous characters in the string where all characters are distinct. We now try to expand the window by adding (j+1)-th character of the string if it is not already in [i, j]. If we cannot, we have an optimal stretch ending at j-th index. To find a new solution we need to shrink the window and we shrink as little as possible. We need to keep track where the window started and the last index where we have seen a character. The resulting algorithm has time and space .

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if(n == 0)
        {
            return 0;
        }
        
        HashMap<Character, Integer> map = new HashMap<>();
        int begin = 0;
        int max = 0;
        int i = 0;
        while(i < n)
        {
            char c = s.charAt(i);
            if(map.containsKey(c) && map.get(c) >= begin) // cannot expand
            {
                max = Math.max(max, i-begin);
                
                // shrink
                begin = map.get(c)+1;
            }
            
            map.put(c, i);
            
            ++i;
        }
        
        return Math.max(max, i-begin);
    }
}


Runtime: 8 ms, faster than 91.96% of Java online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 38.8 MB, less than 28.87% of Java online submissions for Longest Substring Without Repeating Characters.