C++ 中最多包含两个不同字符的最长子字符串
c++server side programmingprogramming
假设我们有一个字符串 s;我们需要找出最多包含两个不同字符的最长子字符串 t 的长度。
因此，如果输入是"eceba"，那么输出将是 3，因为 t 是"ece"。其长度为 3。
为了解决这个问题，我们将遵循以下步骤 −
定义一个函数 lengthOfLongestSubstringKDistinct()，它将接受 s, k,
ans := 0
定义一个映射 m
n := s 的大小，x := 0
初始化 j := 0，i := 0，当 j <= n，更新(j 增加 1)，执行 −
(m[s[j]] 增加 1)
如果 m[s[j]] 等于 1，则 −
(x 增加 1)
while (x > k 且 i <= j)，执行 −
(m[s[i]] 减少 1)
如果 m[s[i]] 等于 0，则 −
(x 减少1)
(将 i 加 1)
ans := ans 和 j - i + 1 中的最大值
返回 ans
在主方法中执行以下操作
返回 lengthOfLongestSubstringKDistinct(s, 2)
示例
让我们看看下面的实现以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k){
int ans = 0;
unordered_map<char, int> m;
int n = s.size();
int x = 0;
for (int j = 0, i = 0; j < n; j++) {
m[s[j]]++;
if (m[s[j]] == 1)
x++;
while (x > k && i <= j) {
m[s[i]]--;
if (m[s[i]] == 0)
x--;
i++;
}
ans = max(ans, j - i + 1);
}
return ans;
}
int lengthOfLongestSubstringTwoDistinct(string s){
return lengthOfLongestSubstringKDistinct(s, 2);
}
};
main(){
Solution ob;
cout << (ob.lengthOfLongestSubstringTwoDistinct("eceba"));
}
输入
"eceba"
输出
3
