3. Longest Substring Without Repeating Characters
Difficulty: Medium
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.
1. 滑动窗口
利用数组记录窗口中是否出现重复字符
- 未出现则继续向右扩大窗口
- 出现则从左侧缩小窗口，直到缩小到没有重复字符
class Solution {
public int lengthOfLongestSubstring(String s) {
int flag[] = new int[128];
int start = 0, end = 0;
int max = 0;
while (end < s.length()) {
if (flag[s.charAt(end)] == 0) {
flag[s.charAt(end++)]++;
max = Math.max(max, end - start);
} else {
while (flag[s.charAt(end)] > 0) {
flag[s.charAt(start++)]--;
}
}
}
return max;
}
}
当然也可以使用HashMap或HashSet来记录窗口中的元素，这里就省略了