C++で解く最長の繰り返し文字置換(スライディングウィンドウ法)

問題の概要

大文字のアルファベットのみで構成された文字列 s が与えられ、この文字列に対して最大 k 回までの操作を行うことができます。1 回の操作では、文字列内の任意の 1 文字を選び、それを別の大文字アルファベットに変更します。操作を終えた後に得られる「すべて同じ文字で構成される部分文字列」の最長の長さを求めるのが、この問題の目的です。

たとえば、入力が "ABAB" で k = 2 の場合、出力は 4 になります。これは、2 つの 'B' を 'A' に置き換える(またはその逆)ことで、文字列全体を同一の文字で構成できるためです。

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

この問題は、スライディングウィンドウ(尺取り法)を使うことで、O(n) の計算量で効率的に解くことができます。

ポイントは、現在のウィンドウ内で最も多く出現している文字の出現回数 maxCount を追跡することです。ウィンドウの長さから maxCount を引いた値は「置換が必要な文字数」を表し、これが k 以下であれば、そのウィンドウ内の部分文字列をすべて同一の文字にできます。条件を満たさなくなったら、ウィンドウの左端 j を進めて縮めていきます。

アルゴリズムの手順

• maxCount = 0、ans = 0 と初期化し、n は文字列 s の長さとします
• サイズ 26 のカウント配列 cnt を用意し、j = 0 とします
• i を 0 から n - 1 までループします
  • cnt[s[i] - 'A'] を 1 増やします
  • maxCount を、maxCount と cnt[s[i] - 'A'] のうち大きい方で更新します
  • j <= i かつ i - j + 1 - maxCount > k の間、次の処理を繰り返します
    • cnt[s[j] - 'A'] を 1 減らします
    • j を 1 増やします
  • ans を、ans と i - j + 1 のうち大きい方で更新します
• 最後に ans を返します

C++での実装例

以下の実装例を見ると、より理解が深まります。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int characterReplacement(string s, int k) {
        int maxCount = 0;
        int ans = 0;
        int n = s.size();
        vector <int> cnt(26);
        int j = 0;
        for(int i = 0; i < n; i++){
            cnt[s[i] - 'A']++;
            maxCount = max(maxCount, cnt[s[i] - 'A']);
            while(j <= i && i - j + 1 - maxCount > k){
                --cnt[s[j] - 'A'];
                j++;
            }
            ans = max(ans, i - j + 1);
        }
        return ans;
    }
};
main(){
    Solution ob;
    cout << ob.characterReplacement("ABAB", 2);
}

入力例

"ABAB"
2

出力例

4

計算量とまとめ

このアルゴリズムでは、各文字が最大 2 回(ウィンドウの拡張時と縮小時)処理されるため、時間計算量は O(n) です。また、使用する配列はサイズ 26 で固定のため、空間計算量は O(1) となります。

「ウィンドウ内で置換が必要な文字数 = ウィンドウの長さ − 最頻文字の出現回数」という考え方は、部分文字列に関するさまざまな問題に応用できる強力なテクニックです。ぜひマスターしておきましょう。