Longest Substring without Repeating Characters
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来装），没有就直接加入，有的话一直删除最左边的字符直到没有重复，这个效率最高。
代码
HashMap
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;
}
}
HashSet
class Solution {
public int lengthOfLongestSubstring(String s) {
int result = 0, left = 0, right = 0;
HashSet<Character> ch = new HashSet<>();
while (right < s.length()) {
if (!ch.contains(s.charAt(right))) {
ch.add(s.charAt(right));
right++;
result = Math.max(result, ch.size());
} else {
ch.remove(s.charAt(left));
left++;
}
}
return result;
}
}
两个索引的滑动窗口用array来存
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;
}
}
滑动窗口
class Solution { public int lengthOfLongestSubstring(String s) { int result = 0, left = 0, right = 0; if (s.isEmpty()) { return result; } HashSet<Character> ch = new HashSet<>(); while (right < s.length()) { if (ch.add(s.charAt(right))) { right++; result = Math.max(result, ch.size()); //ch.size() equal to right - left } else { ch.remove(s.charAt(left)); left++; } } return result; } }
256常数空间
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;
}
}
文档信息
- 本文作者：Ning Huang
- 本文链接：https://ninghuang456.github.io/blog//lc3
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）