C++で文字列をバランスさせるための置換部分文字列の最小長を求める方法

問題の概要

ここでは、「Q」「W」「E」「R」の4種類の文字のみで構成された文字列を扱います。各文字がちょうど n/4 回(n は文字列の長さ)出現するとき、その文字列は「バランスが取れている」と定義します。

元の文字列をバランスの取れた状態にするには、連続する部分文字列を同じ長さの任意の別の文字列で置き換えます。このとき必要となる部分文字列の最小の長さを求めるのが目的です。

例えば、s = "QQWE" の場合、答えは 1 になります。これは先頭の Q を R に置き換えて "RQWE" とすれば、各文字が1回ずつ出現しバランスが取れるためです。また、文字列がすでにバランスしている場合は 0 を返します。

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

この問題はスライディングウィンドウ(尺取り法)を使うことで効率的に解けます。考え方の核心は、「ウィンドウ外の残りの文字数がすべて n/4 以下であれば、そのウィンドウ部分を適切な文字列に置き換えることで全体をバランスさせられる」という点です。

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

• 文字の出現回数を記録するマップ m を用意します。
• s の各文字について出現頻度をマップに格納し、n := s の長さとします。
• res := n(最大値で初期化)、left := 0 とします。
• right を 0 から n − 1 まで動かしながら以下を繰り返します。
  • m[s[right]] を 1 減らします(右端の文字をウィンドウから除外)。
  • left < n かつ m[‘Q’] ≤ n/4 かつ m[‘W’] ≤ n/4 かつ m[‘E’] ≤ n/4 かつ m[‘R’] ≤ n/4 である間:
    • res := min(res, right − left + 1)(現在のウィンドウ幅で答えを更新)
    • m[s[left]] を 1 増やします(左端の文字をウィンドウに戻す)。
    • left を 1 増やします。
• 最後に res を返します。

それでは、実際の実装を見て理解を深めましょう。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int balancedString(string s) {
        unordered_map <char, int> m;
        for(int i = 0;i<s.size();i++)m[s[i]]++;
        int n = s.size();
        int res = n;
        int left = 0;
        for(int right = 0;right<n;right++){
            m[s[right]]--;
            while(left<n && m['Q']<=n/4 && m['W'] <=n/4 && m['E'] <=n/4 && m['R']<=n/4){
                res = min(res, right - left + 1);
                m[s[left]]+=1;
                left++;
            }
        }
        return res;
    }
};
main(){
    Solution ob;
    cout << (ob.balancedString("QQEQ"));
}

入力

"QQEQ"

出力

2

計算量について

この実装では、右ポインタと左ポインタがそれぞれ最大でも文字列の長さ n 回しか移動しないため、時間計算量は O(n)、空間計算量は O(1)(固定サイズのマップ)となります。文字列が長くなっても高速に動作するのが特徴です。