滑动窗口题目(难题)

5.Longest Substring with Distinct Characters (hard)

问题描述

给定一个字符串，找出拥有不同字符的最长子字符串的长度。
Example 1:

Input: String="aabccbb"
Output: 3
Explanation: The longest substring with distinct characters is "abc".
1
2
3

Example 2:

Input: String="abbbb"
Output: 2
Explanation: The longest substring with distinct characters is "ab".
1
2
3

Example 3:

Input: String="abccde"
Output: 3
Explanation: Longest substrings with distinct characters are "abc" & "cde".
1
2
3

解题的关键：

1.本题相当经典，算是滑动窗口类题目的代表题目。解决起来需要一点技巧。首先，老话重提，最重要的是窗口收缩的时机: 本题收缩的时机是窗口内出现重复的字母的时侯，思考的时候切记这点。
2.窗口内出现重复的字母的时侯，我们仍然可以用hash_map来存储，key存字母，value存字母出现的次数，或key存字母，value存字母最早出现的位置也可，因为要求的是字符串的长度，就要用到窗口尾部位置减去头部位置

	int lengthOfLongestSubstring(string s) {
			int winstart = 0,ans=0;
			unordered_map<char,int> cnt;
			for(int winend=0;winend<s.size();i++){
				cnt[s[winend]]++;
				while(cnt[s[winend]] == 2)//当窗口内的某个字母个数等于2时收缩
				 {cnt[s[winstart ]]--,winstart ++;}//收缩
				ans = max(ans , winend-winstart +1);
			}
			return ans;
		}
1
2
3
4
5
6
7
8
9
10
11

6.Longest Substring with Same Letters after Replacement (hard)

问题描述

给定一个只有小写字母的字符串，如果允许用任意字母替换不超过 k 个字母，求替换后具有相同字母的最长子串的长度。
Example 1:

Input: String="aabccbb", k=2
Output: 5
Explanation: Replace the two 'c' with 'b' to have the longest repeating substring "bbbbb".
1
2
3

Example 2:

Input: String="abbcb", k=1
Output: 4
Explanation: Replace the 'c' with 'b' to have the longest repeating substring "bbbb".
1
2
3

Example 3:

Input: String="abccde", k=1
Output: 3
Explanation: Replace the 'b' or 'd' with 'c' to have the longest repeating substring "ccc".
1
2
3

解题的关键：

1.老活了，关键在于窗口收缩的时机，以例一来说"aabccbb"，k=2，窗口应该在 窗口总大小大于窗口内重复次数最多的字母个数 + 可替换的k个字母数。窗口为“aabcc”时该收缩了，因为此时重复字母（a或者c）最多重复了2次，k=2，5>2+2，而2+2就是一个可能的答案，懂得都懂。
2.本题除了hash_map，还需要有一个变量来存储窗口内重复次数最多的字母个数，涉及到字母个数，所以map 的key储存字母，value储存字母个数。

 int findLength(const string &str, int k) {
    int windowStart = 0, maxLength = 0, maxRepeatLetterCount = 0;
    unordered_map<char, int> letterFrequencyMap;
    for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
      char rightChar = str[windowEnd];
      letterFrequencyMap[rightChar]++;
      //窗口内部可能有多个字母重复，要记录重复次数最多的

      maxRepeatLetterCount = max(maxRepeatLetterCount, letterFrequencyMap[rightChar]);
      //收缩时机为窗口大小-最多重复次数>可替换次数k
      if (windowEnd - windowStart + 1 - maxRepeatLetterCount > k) 
      {
        char leftChar = str[windowStart];
        letterFrequencyMap[leftChar]--;
        windowStart++;
      }

      maxLength = max(maxLength, windowEnd - windowStart + 1);
    }

    return maxLength;
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

7.Longest Substring with Same Letters after Replacement (hard)

问题描述

给定一个包含 0 和 1 的数组，如果允许用 1 替换不超过“k”个 0，请找出全为 1 的最长连续子数组的长度。
Example 1:

Input: Array=[0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1], k=2
Output: 6
Explanation: Replace the '0' at index 5 and 8 to have the longest contiguous subarray of 1s having length 6.
1
2
3

Example 2:

Input: Array=[0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1], k=3
Output: 9
Explanation: Replace the '0' at index 6, 9, and 10 to have the longest contiguous subarray of 1s having length 9.
1
2
3

1.和上题基本类似，解题的核心思路是一样的
2.因为只有"0",“1”，所以没有必要用map来记录个数，找的是全为 1 的最长连续子数组的长度，所以我们只需要一个变量来记录窗口内“1”的个数即可，“1”进入窗口个数加一，“1”收缩出窗口个数减一

 int findLength(const vector<int>& arr, int k) {
    int windowStart = 0, maxLength = 0, maxOnesCount = 0;

    for (int windowEnd = 0; windowEnd < arr.size(); windowEnd++) {
      if (arr[windowEnd] == 1) {
        maxOnesCount++;
      }
      if (windowEnd - windowStart + 1 - maxOnesCount > k) {
        if (arr[windowStart] == 1) {
          maxOnesCount--;
        }
        windowStart++;
      }

      maxLength = max(maxLength, windowEnd - windowStart + 1);
    }

    return maxLength;
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19