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

文字列sがあるとします。最大で2つの異なる文字を持つ最長の部分文字列tの長さを見つける必要があります。

したがって、入力が「eceba」のような場合、tは「ece」で長さが3であるため、出力は3になります。

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

• 関数lengthOfLongestSubstringKDistinct（）を定義します。これには、s、k、

  が必要です。

• 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を返す

• メインの方法から次のようにします

• 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