3. Longest Substring Without Repeating Characters

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.

Solution

  1. Sliding Window
    维护区间[start, end], 则初始值start = 0, end = 0. 当s[end]重复时,从set中删掉s[start], 否则加入s[end]至set,并更新答案(因为end向后移动区间长度一定是增大的)。

  2. Optimized Sliding Window
    使用HashMap记录每一个char对应的索引,需要更新start时,直接从HashMap中取出即可。
    维护区间(start, end], 则初始值start = -1, end = 0

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() ==0) return 0;
int res = 0, n = s.length();
int start = 0, end = 0;
HashSet<Character> set = new HashSet<>();
while(start < n && end < n){
if(!set.contains(s.charAt(end))){
set.add(s.charAt(end));
res = Math.max(res, end - start + 1);
end++;
}else{
set.remove(s.charAt(start++));
}
}

return res;
}