05 August 2008
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given “abcabcbb”, the answer is “abc”, which the length is 3.
Given “bbbbb”, the answer is “b”, with the length of 1.
Given “pwwkew”, 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）首先可以用一个HashMap来记录窗口内的字符和这些字符最后出现的位置，如果窗口右侧移动后发现有重复的字符，那就将left索引指向HashMap里面保存的该字符的位置的下一位，窗口右侧继续移动，同时保持len的最长的值；
2）使用HashSet，出现过的字符都放入set中，遇到set中没有的字符就加入set并更新结果result，如果有重复的，从左边开始删除字符，知道删到重复的字符为止。
3）两个索引的滑动窗口，左索引和右索引，当右边新进来字符时，检查有没有重复（用一个array来装），没有就直接加入，有的话一直删除最左边的字符直到没有重复，这个效率最高。
优先掌握HashSet做法
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
27
28
29
30
31
32
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
// Create a set to store unique characters
HashSet<Character> set = new HashSet<>();
int maxLength = 0; // Maximum length of substring without repeating characters
int left = 0; // Left pointer of the sliding window
int right = 0; // Right pointer of the sliding window
while (right < n) {
// If the current character is not in the set
if (!set.contains(s.charAt(right))) {
// Add the current character to the set
set.add(s.charAt(right));
// Update the maximum length if necessary
maxLength = Math.max(maxLength, right - left + 1);
// Move the right pointer to expand the window
right++;
} else {
// If the current character is already in the set
// Remove the character at the left pointer from the set
set.remove(s.charAt(left));
// Move the left pointer to shrink the window
left++;
}
}
return maxLength;
}
}
HashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> map = new HashMap<>(); // k-v: 字符-最新位置
int result = 0;
for (int left = 0, right = 0; right < s.length(); right++) {
if (map.containsKey(s.charAt(right))) {
left = Math.max(left, map.get(s.charAt(right)) + 1); // 更新一下把left的位置+1
}
map.put(s.charAt(right), right); //不管是否移动左边的索引，都将当前的字符存入hashmap
result = Math.max(result, right - left + 1);
}
return result;
}
}
两个索引的滑动窗口用array来存
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] freq = new int[256];
int left = 0;
int right = -1; // 刚开始设定窗口里面什么都没有
int result = 0;
while (right + 1 < s.length()) {
if (right + 1 < s.length() && freq[s.charAt(right + 1)] == 0) {
freq[s.charAt(right + 1)] = 1;
right++;
} else { //freq[s.charAt(right + 1)] == 1
//移掉一个左边的字符，并减掉相应的freq
//一直到减掉重复的字符之前，虽然有重复的字符，但中间不会是最长的子字符串
freq[s.charAt(left)]--;
left++;
}
result = Math.max(result, right - left + 1);
}
return result;
}
}
滑动窗口
256常数空间
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
27
28
29
30
31
32
33
34
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.isEmpty()) {
return 0;
}
int result = 1;
int slow = 0;
int fast = 0;
int[] count = new int[256];
while (slow < s.length() && fast < s.length()) {
char ch = s.charAt(fast);
count[ch - 'a']++;
if (count[ch - 'a'] == 2) { // 只要多于1个
// 更新最大值
result = Math.max(result, fast - slow);
// remove dups
while (slow <= fast) {
count[s.charAt(slow) - 'a']--; // 逐个缩小窗口直到没有dups
if (count[ch - 'a'] == 1) { // fast所在的元素减得只剩1个，窗口中没有重复了
slow++;
break;
}
slow++;
}
} else {
fast++;
}
}
return result;
}
}