数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中最多包含两个不同字符的最长子串
假设我们有一个字符串s；我们必须找到最长子串t的长度，该子串最多包含2个不同的字符。
因此，如果输入类似于“eceba”，则输出将为3，因为t是“ece”，其长度为3。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数lengthOfLongestSubstringKDistinct()，它将接收s和k作为参数，
ans := 0
定义一个map m
n := s的长度，x := 0
用于初始化j := 0，i := 0，当j < n时，更新（j增加1），执行：
(m[s[j]]增加1)
如果m[s[j]]等于1，则：
(x增加1)
当(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
更新于：2020年11月18日
1K+ 次浏览
广告