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

問題概要

文字列が与えられたとき、最大 k 個の異なる文字を含む最長の部分文字列 T の長さを求めるのがこの問題の目的です。

例えば、入力が s = "eceba"、k = 2 の場合、出力は 3 になります。これは T = "ece" となり、その長さが 3 であるためです。

解法のアプローチ：スライディングウィンドウ

この問題はスライディングウィンドウ（尺取り法）とハッシュマップを組み合わせることで、線形時間 O(n) で効率的に解くことができます。

具体的な手順は以下の通りです。

• ans := 0（答えとなる最長の長さ）

• マップ m を定義する（ウィンドウ内の各文字の出現回数を記録）

• n := 文字列 s のサイズ

• x := 0（現在のウィンドウに含まれる異なる文字の種類数）

• j := 0、i := 0 で初期化し、j < n の間 j を 1 ずつ増やしながら次を繰り返します。

  • 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 := ans と (j − i + 1) のうち大きい方を代入する

• 最後に ans を返します。

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

入力

"eceba", 2

出力

3

動作のポイントと計算量

右端のポインタ j が文字列を先頭から順に走査し、異なる文字の種類数 x が k を超えた瞬間に、左端のポインタ i を進めてウィンドウを縮小します。これにより、常に「異なる文字が k 種類以内」という条件を満たすウィンドウを維持しながら、最大長を更新していきます。

• 時間計算量： O(n) — 各文字はポインタ i と j によってそれぞれ高々 1 回しか処理されないため

• 空間計算量： O(k) — マップには最大でも k+1 種類の文字しか保持されないため