C ++中带有最多两个不同字符的最长子字符串
假设我们有一个字符串s;我们必须找到具有最多2个不同字符的最长子字符串t的长度。
因此,如果输入类似于“eceba”,则输出将为3,因为t为“ece”,其长度为3。
为了解决这个问题,我们将遵循以下步骤-
定义一个函数lengthOfLongestSubstringKDistinct()
,它将取s,k,
回答:=0
定义一张映射
n:=s的大小,x:=0
对于初始化j:=0,i:=0,当j<n时,更新(j增加1),-
(将m[s[i]]减1)
如果m[s[i]]等于0,则-
(将i增加1)
(将x减少1)
(将x增加1)
(将m[s[j]]增加1)
如果m[s[j]]与1相同,则-
而(x>k并且i<=j),做-
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