[刷题]无重复子串-滑动窗口问题
文章目录
问题描述
最长无重复子串问题:
找到一个字符串中不含有重复字符的最长连续子串如"pwwkew"的解为"wke"
这个问题难点在于如何保证当前的子串是无重复的,
换句话说,来了一个重复的字符该怎么处理?
1.我们肯定不允许子串中有重复的字符,那么我们用一个窗口维护一个无重复字符的子串,
2.如果新字符不是重复字符,直接将右边界滑至该字符。
3.当来了一个重复字符时,思考窗口怎么移动。截至该字符之前的最长子串我们已经求得,所以我们可以放心的滑动左边界,丢弃一些元素直至该字符不再是重复字符,同时,我们把右边界滑到当前字符。通过这样做,我们能保证我们在往后遍历的过程中依然维护了一个无重复的子串。
如"abca"到第二个'a'时,窗口左边界滑到'b',右边界滑到'a'
4.每次窗口调整结束之后,计算当前子串的长度。
模板代码如下,有一些细节需要注意
public int lengthOfLongestSubstring(String s) {
// map记录每种字符最新的下标
HashMap<Character, Integer> map = new HashMap<>();
int start = 0; // 当前子串的起始位置
int maxlen = 0;
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
// 如果map中包含该字符,可能需要滑动窗口
// 为什么说“可能”: 这个字符可能在之前的子串中出现过,并且滑动窗口已经滑过该字符
// 如 "bacab" 当右边界到达第二个'a'时, start的位置为上一个'a'的位置+1 即为'c'的位置
// 但此时右边界到底'b'时,虽然map中包含'b',但我们不能把左边界移到上一个'b'的位置+1,
// 因为窗口已经划过了那个位置,所以我们需要取max(左边界, 上一个该字符的位置+1)
if(map.containsKey(c)){
start = Math.max(start,map.get(c)+1);
}
// 更新字符的位置
map.put(c, i);
maxlen = Math.max(maxlen,i-start+1);
}
return maxlen;
}
相关题目
Leetcode
3.无重复字符的最长子串
30.串联所有单词的子串
76.最小覆盖子串
159.至多包含两个不同字符的最长子串
209.长度最小的子数组
239.滑动窗口最大值
567.字符串的排列
632.最小区间
727.最小窗口子序列
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。
示例 1:
输入:
s = "barfoothefoobarman",
words = ["foo","bar"]
输出:[0,9]
解释:
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2:
输入:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
输出:[]
这道题使得窗口内的元素不再是单个数或者字符,而是一个string,考虑如何控制窗口内符合条件的元素个数?窗口移动的条件?遍历如何进行?遍历的区间?
注意条件"长度相同的单词",为这道题提供了很多方便,这样每次移动的距离从基本题目的1变为了word_len单词的长度。
但子串遍历若从0开始,以word_len为一步,并不能覆盖到所有可能的子串,因此需要以[0.word_len-1]都作为子串的开始位置各遍历一遍,而后面为什么不需要了,因为窗口移动的过程中已经把后面的情况包括了,具体看代码
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> ans = new ArrayList<>();
if(s.length()==0||words.length==0) return ans;
int word_len = words[0].length();
int word_num = words.length;
if(word_len*word_num>s.length()) return ans;
HashMap<String , Integer> hasMap = new HashMap<>();
for(String word : words) hasMap.put(word,hasMap.getOrDefault(word,0)+1);
// 以i为子串起点, 但i只能到word_len-1,否则可能出现重复解,
// 比如有些窗口left 缩减到 >= word_len 这相当于又遍历了一遍
for(int i=0;i<word_len;i++){
int left = i; // 窗口左边界
int right = i; // 窗口右边界
int n=0;
HashMap<String, Integer> counter = new HashMap<>();//记录单词个数
// 不断扩大右边界
while (right+word_len<=s.length()){
String tmp_word = s.substring(right, right+word_len);
// 如果出现了words 以为的单词,则直接把窗口左边界移到该单词后面,并清空counter
if(!hasMap.containsKey(tmp_word)){
right += word_len;
left = right;
counter.clear();
n=0;
}
else {
counter.put(tmp_word,counter.getOrDefault(tmp_word,0)+1);
n++;
// 如果出现了多余的单词,则缩小左边界 直到不再重复
while (counter.get(tmp_word)>hasMap.getOrDefault(tmp_word,0)){
String rm_word = s.substring(left,left+word_len);
counter.put(rm_word,counter.get(rm_word)-1);
n--;
left += word_len;
}
right+=word_len;
if(n==word_num) {
ans.add(left);
}
}
}
}
return ans;
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论