数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中最长重复字符替换
假设我们给定一个只包含大写字母的字符串 s，我们最多可以在该字符串上执行 k 次操作。在一次操作中，我们可以选择字符串的任何字符并将其更改为任何其他大写字母。我们必须找到在执行上述操作后可以获得的最长包含所有重复字母的子字符串的长度。因此，如果输入类似于：“ABAB”并且 k = 2，则输出将为 4。这是因为两个 'A' 和两个 'B'，反之亦然。
为了解决这个问题，我们将遵循以下步骤：
- maxCount := 0，ans := 0，n := 字符串 s 的大小
- 创建一个大小为 26 的数组 cnt，j := 0
- 对于 i := 0 到 n – 1
- 将 cnt[s[i] – ‘A’] 加 1
- maxCount := maxCount 和 count[s[i] – ‘A’] 的最大值
- 当 j <= i 且 i – j + 1 – maxCount > k 时，执行以下操作：
- 将 cnt[s[j] – ‘A’] 减 1
- 将 j 加 1
- ans := ans 和 i – j + 1 的最大值
- 返回 ans
示例 (C++)
让我们看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int characterReplacement(string s, int k) {
int maxCount = 0;
int ans = 0;
int n = s.size();
vector <int> cnt(26);
int j = 0;
for(int i = 0; i < n; i++){
cnt[s[i] - 'A']++;
maxCount = max(maxCount, cnt[s[i] - 'A']);
while(j <= i && i - j + 1 - maxCount > k){
--cnt[s[j] - 'A'];
j++;
}
ans = max(ans, i - j + 1);
}
return ans;
}
};
main(){
Solution ob;
cout << ob.characterReplacement("ABAB", 2);
}输入
"ABAB" 2
输出
4
更新于：2020年4月28日
1K+ 次浏览
广告