424. 替换后的最长重复字符
题目
424. 替换后的最长重复字符 难度：medium
给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。
在执行上述操作后，返回包含相同字母的最长子字符串的长度。
示例 1：
代码语言：javascript复制输入： s = "ABAB", k = 2
输出： 4
解释： 用两个'A'替换为两个'B',反之亦然。示例 2：
代码语言：javascript复制输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。提示：
1 <= s.length <= 10^5s仅由大写英文字母组成0 <= k <= s.length
方法一：滑动窗口
思路
有时候题做多了，一上来总是想着如何最优解，其实，可以先用最简单的方法 -- 暴力将题目先解出来，然后再进行优化，这里也是一样的；
通过暴力枚举输入字符串的 所有 子串，对于每一个子串：
- 如果子串里所有的字符都一样，就考虑长度更长的子串；
- 如果当前子串里出现了至少两种字符，要想使得替换以后所有的字符都一样，并且重复的、连续的部分更长，应该替换掉出现次数最多字符 以外 的字符。
那根据暴力解法的缺点，可以做出以下的优化：
- 不要重复扫描；
- 没必要考虑长度小于等于当前最长子串长度的子串；
以 s = AABCABBB，k = 2 为例，寻找替换 k 次以后字符全部相等的最长子串的长度的过程如下图所示：
- 右边界先移动找到一个满足题意的可以替换
k个字符以后，所有字符都变成一样的当前看来最长的子串，直到右边界纳入一个字符以后，不能满足的时候停下； - 然后考虑左边界向右移动，左边界只须要向右移动一格以后，右边界就又可以开始向右移动了，继续尝试找到更长的目标子串；
- 替换后的最长重复子串就产生在右边界、左边界交替向右移动的过程中。
解题
Python：
代码语言：javascript复制class Solution:
def characterReplacement(self, s: str, k: int) -> int:
n = len(s)
count = [0]*26
max_cnt = 0
j = 0
ans = 0
for i in range(n):
while j < n and j-i 1-max(max_cnt, count[ord(s[j])-ord('A')] 1) <= k:
count[ord(s[j])-ord('A')] = 1
if count[ord(s[j])-ord('A')] > max_cnt:
max_cnt = count[ord(s[j])-ord('A')]
j = 1
if j-i > ans:
ans = j-i
if j == n:
break
count[ord(s[i])-ord('A')] -= 1
if count[ord(s[i])-ord('A')] 1 == max_cnt:
max_cnt = max(count)
return ansJava：
代码语言：javascript复制public class Solution {
public int characterReplacement(String s, int k) {
int len = s.length();
if (len < 2) {
return len;
}
char[] charArray = s.toCharArray();
int left = 0;
int right = 0;
int res = 0;
int maxCount = 0;
int[] freq = new int[26];
// [left, right) 内最多替换 k 个字符可以得到只有一种字符的子串
while (right < len){
freq[charArray[right] - 'A'] ;
// 在这里维护 maxCount，因为每一次右边界读入一个字符，字符频数增加，才会使得 maxCount 增加
maxCount = Math.max(maxCount, freq[charArray[right] - 'A']);
right ;
if (right - left > maxCount k){
// 说明此时 k 不够用
// 把其它不是最多出现的字符替换以后，都不能填满这个滑动的窗口，这个时候须要考虑左边界向右移动
// 移出滑动窗口的时候，频数数组须要相应地做减法
freq[charArray[left] - 'A']--;
left ;
}
res = Math.max(res, right - left);
}
return res;
}
}438. 找到字符串中所有字母异位词
题目
438. 找到字符串中所有字母异位词 难度：medium
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
代码语言：javascript复制输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。示例 2:
代码语言：javascript复制输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。提示:
1 <= s.length, p.length <= 3 * 10^4s和p仅包含小写字母
方法一：滑动窗口
思路
根据题目要求，我们需要在字符串 s 寻找字符串 p 的异位词。因为字符串 p 的异位词的长度一定与字符串 p 的长度相同，所以我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p 的异位词。
这里可以使用数组来存储字符串 p 和滑动窗口中每种字母的数量。当字符串 s 的长度小于字符串 p 的长度时，字符串 s 中一定不存在字符串 p 的异位词。但是因为字符串 s 中无法构造长度与字符串 p 的长度相同的窗口，所以这种情况需要单独处理。
解题
Python：
代码语言：javascript复制class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
s_len, p_len = len(s), len(p)
if s_len < p_len:
return []
ans = []
count = [0] * 26
for i in range(p_len):
count[ord(s[i]) - 97] = 1
count[ord(p[i]) - 97] -= 1
differ = [c != 0 for c in count].count(True)
if differ == 0:
ans.append(0)
for i in range(s_len - p_len):
if count[ord(s[i]) - 97] == 1: # 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
differ -= 1
elif count[ord(s[i]) - 97] == 0: # 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
differ = 1
count[ord(s[i]) - 97] -= 1
if count[ord(s[i p_len]) - 97] == -1: # 窗口中字母 s[i p_len] 的数量与字符串 p 中的数量从不同变得相同
differ -= 1
elif count[ord(s[i p_len]) - 97] == 0: # 窗口中字母 s[i p_len] 的数量与字符串 p 中的数量从相同变得不同
differ = 1
count[ord(s[i p_len]) - 97] = 1
if differ == 0:
ans.append(i 1)
return ansJava：
代码语言：javascript复制class Solution {
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length(), pLen = p.length();
if (sLen < pLen) {
return new ArrayList<Integer>();
}
List<Integer> ans = new ArrayList<Integer>();
int[] count = new int[26];
for (int i = 0; i < pLen; i) {
count[s.charAt(i) - 'a'];
--count[p.charAt(i) - 'a'];
}
int differ = 0;
for (int j = 0; j < 26; j) {
if (count[j] != 0) {
differ;
}
}
if (differ == 0) {
ans.add(0);
}
for (int i = 0; i < sLen - pLen; i) {
if (count[s.charAt(i) - 'a'] == 1) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
--differ;
} else if (count[s.charAt(i) - 'a'] == 0) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
differ;
}
--count[s.charAt(i) - 'a'];
if (count[s.charAt(i pLen) - 'a'] == -1) { // 窗口中字母 s[i pLen] 的数量与字符串 p 中的数量从不同变得相同
--differ;
} else if (count[s.charAt(i pLen) - 'a'] == 0) { // 窗口中字母 s[i pLen] 的数量与字符串 p 中的数量从相同变得不同
differ;
}
count[s.charAt(i pLen) - 'a'];
if (differ == 0) {
ans.add(i 1);
}
}
return ans;
}
}
