C ++中具有最多K个不同字符的最长子字符串

假设我们有一个字符串；我们必须计算包含最多k个不同字符的最长子字符串T的长度。

因此，如果输入像s =“ eceba”，k = 2，则输出将为3，因为T为“ ece”，其长度为3。

为了解决这个问题，我们将遵循以下步骤-

• 回答：= 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

例 

让我们看下面的实现以更好地理解-

#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;
   }
};
main() {
   Solution ob;
   cout << (ob.lengthOfLongestSubstringKDistinct("eceba", 2));
}

输入值

"eceba", 2

输出结果

3