数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中交换以获取最长重复字符子字符串
假设我们有一个字符串 text，我们允许交换字符串中的两个字符。我们需要找到具有重复字符的最长子字符串的长度。例如，如果输入是“ababa”，则结果将是 3，因为如果我们将第一个 b 与最后一个 a 交换，或者将最后一个 b 与第一个 a 交换，则最长的重复字符将是“aaa”，因此长度为 3。
为了解决这个问题，我们将遵循以下步骤：
定义一个映射 cnt，设置 ret := 1，j := 0，n := text 的大小，v := 0，定义一个名为 x 的集合，并创建另一个名为 m 的映射，m 将保存 text 中每个字符的频率。
设置 a := * 和 b := *
对于 i 从 0 到 n 的范围
将 cnt[text[i]] 增加 1
将 text[i] 插入到 x 中
如果 cnt[text[i]] 等于 2，则
如果 a 是 *，则 a := text[i]，否则 b := text[i]
如果 a 不是 * 并且 b 也不是 * 或 x 的大小大于 2
将 cnt[text[j]] 减少 1
如果 cnt[text[j]] 等于 1，则
如果 text[j] 等于 a，则设置 a := *，否则 b := *
如果 cnt[text[j]] 等于 0，则从 x 中删除 text[j]
greater := 如果 cnt[a] > cnt[b] 则为 a，否则为 b
如果 x 的大小为 1 或 m[greater] – cnt[greater] 不为 0，则
ret := ret 和 i – j + 1 的最大值
否则 ret := ret 和 i – j 的最大值
返回 ret。
让我们看看以下实现以获得更好的理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxRepOpt1(string text) {
int ret = 1;
map <char, int> cnt;
int j = 0;
int n = text.size();
int v = 0;
set <char> x;
map <char, int> m;
for(int i = 0; i < text.size(); i++)m[text[i]]++;
char a = '*', b ='*';
for(int i = 0; i < n; i++){
cnt[text[i]]++;
x.insert(text[i]);
if(cnt[text[i]] == 2){
if(a == '*'){
a = text[i];
}else{
b = text[i];
}
}
while(a != '*' && b != '*' || x.size() > 2){
cnt[text[j]]--;
if(cnt[text[j]] == 1) {
if(text[j] == a) {
a ='*';
}else{
b = '*';
}
}
if(cnt[text[j]] == 0) x.erase(text[j]);
j++;
}
char greater = cnt[a] > cnt[b] ? a : b;
if(x.size() == 1 || m[greater] - cnt[greater]){
ret = max(ret, i - j + 1);
}else{
ret = max(ret, i - j);
}
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.maxRepOpt1("ababa"));
}输入
"ababa"
输出
3
更新于: 2020年4月30日
489 次查看
广告