C++で最大K個の異なる文字を含む最長のサブストリング

したがって、入力がs ="eceba"、k =2の場合、Tは "ece"であり、長さは3であるため、出力は3になります。

これを解決するには、次の手順に従います-

• ans：=0

• 1つのマップを定義するm

• n：=sのサイズ

• x：=0

• 初期化j：=0、i：=0の場合、j

  • （m [s [j]]を1増やします）

  • m [s [j]]が1と同じ場合、-

    • （xを1増やします）

  • （x>kおよびi<=j）、do −

    • （m [s [i]]を1減らします）

    • m [s [i]]が0と同じ場合、-

      • （xを1減らします）

    • （iを1増やします）

  • 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