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.

Thinking

关键字：子串，无重复，马上想到的就是sliding window + HashSet策略：维护一个滑动窗口，保证这个窗口内没有重复的字符。

Solution

用i和j作为滑动窗口的双指针，对于每个位置j，都试图缩小窗口来保证窗口内没有重复字符。
同时使用一个boolean[256]的数组来作为哈希表。256是扩展ASCII码的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public int (String s) {
    int result = 0;
    boolean[] visited = new boolean[256];
    int i = 0;
    for (int j = 0; j < s.length(); j++) {
        char ch = s.charAt(j);
        while (visited[ch]) {
            visited[s.charAt(i)] = false;
            i++;
        }
        visited[ch] = true;
        result = Math.max(result, j - i + 1);
    }
    return result;
}

时间复杂度：O(N)。N是字符串的长度
空间复杂度：O(1)。因为我们使用的额外空间是常数256，它不会随着字符串长度的增加而变大