3. Longest Substring Without Repeating Characters

Sliding Window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0; // 注意题目中的字符串长度可能为 0，所以此处最大值默认为 0

        int[] windowMap = new int[256]; // 注意不仅仅是英文字母，所以此处使用了 256
        int i = 0; // window: [i, j]
        for (int j = 0; j < s.length(); j++) {
            char c = s.charAt(j);
            windowMap[c]++;

            while (windowMap[c] > 1) {
                char leftmost = s.charAt(i);
                windowMap[leftmost]--;
                i++;
            }

            maxLength = Math.max(maxLength, j - i + 1);
        }

        return maxLength;
    }
}

此解法为添加至窗口后再移除重复元素。

Sliding Window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0; // 注意题目中的字符串长度可能为 0，所以此处最大值默认为 0

        boolean[] windowMap = new boolean[256]; // 注意不仅仅是英文字母，所以此处使用了 256
        int i = 0; // window: [i, j]
        for (int j = 0; j < s.length(); j++) {
            char c = s.charAt(j);
            while (windowMap[c]) {
                char leftmost = s.charAt(i);
                windowMap[leftmost] = false;
                i++;
            }

            windowMap[c] = true; // 不要忘记更新窗口中的标记
            maxLength = Math.max(maxLength, j - i + 1);
        }

        return maxLength;
    }
}

此解法为添加至窗口前移除重复元素，相比上方解法，此解法可使用 boolean 数组，更节省空间。

Sliding Window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        Map<Character, Integer> valueToPrevIndexMap = new HashMap<>();

        int i = 0; // window: [i, j]
        for (int j = 0; j < s.length(); j++) {
            char c = s.charAt(j);
            Integer prevIndex = valueToPrevIndexMap.get(c);
            if (prevIndex != null) {
                // 出现了重复字符，重置窗口起点
                // ['a', 'b', 'c', 'a', 'b', 'c'], 当遇到第二个 'a' 时，i 移动至第一个 'a' 的下一个位置
                // 注意此处一定要使用 Math.max, 避免指针 i 回退
                // ['a', 'b', 'b', 'a'], 避免遍历至第二个 'a' 时 i 从 'b' 回退至第一个 'a' 的下一个位置
                i = Math.max(i, prevIndex + 1);
            }

            valueToPrevIndexMap.put(c, j);
            maxLength = Math.max(maxLength, j - i + 1);
        }

        return maxLength;
    }
}

此解法中的 HashMap 持有的为遍历过的元素与索引的映射，遍历过程中不会移除映射，因为该解法中途不移除映射，导致对 i 的更新需要使用 Math.max 保证 i 只能增大。

References

3. Longest Substring Without Repeating Characters
剑指 Offer 48. 最长不含重复字符的子字符串
剑指 Offer II 016. 不含重复字符的最长子字符串