C++で最大2種類の異なる文字を含む最長部分文字列を求める方法

文字列 s が与えられたとき、異なる文字が最大2種類まで含まれる最長の部分文字列 t の長さを求める問題を考えてみましょう。

例えば、入力が "eceba" の場合、出力は 3 になります。これは条件を満たす最長の部分文字列が "ece" であり、その長さが 3 だからです。

この問題はスライディングウィンドウ（尺取り法）を使うことで効率的に解けます。各文字の出現回数をハッシュマップで管理し、異なる文字の種類数が2を超えたら左端から縮めていくというアプローチです。

解法の手順

• 関数 lengthOfLongestSubstringKDistinct() を定義します。引数として文字列 s と許容する異なる文字数 k を受け取ります。

• 答えを格納する変数 ans := 0 で初期化します。

• 文字の出現回数を記録するマップ m を定義します。

• n := s のサイズ、x := 0（現在のウィンドウ内の異なる文字の種類数）とします。

• j := 0、i := 0 で初期化し、j < n の間ループを実行します（j は右端ポインタ）。

  • 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 := max(ans, j - i + 1) として、これまでの最大長を更新します。

• 最後に ans を返します。

• メインメソッドからは lengthOfLongestSubstringKDistinct(s, 2) を呼び出して結果を取得します。

実装例

理解を深めるために、以下の C++ 実装を見てみましょう。

#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

計算量について

このアルゴリズムでは、右端ポインタ j と左端ポインタ i がそれぞれ文字列を高々1周するだけなので、時間計算量は O(n)、マップに格納される文字の種類は最大3種類程度に抑えられるため、空間計算量も O(1)（文字種が有限の場合）となります。非常に効率的な解法と言えるでしょう。