Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

O(n) time, O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        if (length == 0){return 0;}
        int max = 0;
        HashMap<Character,Integer> cache = new HashMap<Character, Integer>();
        for (int i = 0, j = 0; i < length; i++){
            if (cache.containsKey(s.charAt(i))){
                // if the char has appeared before, move the left pointer to the right of the previous position
                // compare with the current j value
                // test case "abba" will not if not compare with j
                j = Math.max(j,cache.get(s.charAt(i)) + 1);
            }
            cache.put(s.charAt(i), i);
            max = Math.max(max, i - j + 1);
        }
        
        return max;
    }
}

O(n) time O(n) space set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            } else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}