Poison

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
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        Set<Character> set = new HashSet<>();

        // subString: [i, j]
        int i = 0;
        for (int j = 0; j < s.length(); j++) {
            char c = s.charAt(j);
            while (set.contains(c)) {
                set.remove(s.charAt(i));
                i++;
            }

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

        return maxLength;
    }
}

此解法中的 HashSet 持有的为当前窗口中的元素。

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[] windowMap = new int[256];

        int maxLength = 0;
        int i = 0;
        for (int j = 0; j < s.length(); j++) {
            // window: [i, j]
            
            char rightmost = s.charAt(j);
            windowMap[rightmost]++;

            while (windowMap[rightmost] > 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
22
23
24
25
26
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> valueToPrevIndexMap = new HashMap<>();
        int maxLength = 0;

        int i = 0;
        for (int j = 0; j < s.length(); j++) {
            // window: [i, j]

            char rightmost = s.charAt(j);
            Integer prevIndex = valueToPrevIndexMap.get(rightmost);
            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(rightmost, j);
            maxLength = Math.max(maxLength, j - i + 1);
        }

        return maxLength;
    }
}

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

Reference

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