C++で文字列を最大個数のバランス文字列に分割する方法

「バランスの取れた文字列（balanced string）」とは、'L' と 'R' という2種類の文字が同数ずつ含まれている文字列のことです。この記事では、バランスの取れた文字列 s が与えられたとき、それをできるだけ多くのバランスの取れた部分文字列に分割し、その最大個数を求める方法を C++ で解説します。

例えば、入力が "RLRRLLRLRL" の場合、出力は 4 になります。これは "RL"、"RRLL"、"RL"、"RL" の4つの部分文字列に分割でき、それぞれが同数の L と R を含んでいるためです。

アルゴリズムの考え方

以下の手順で問題を解きます。

1. カウンタ cnt と答え ans を 0 で初期化する。
2. 開始位置 i を先頭から順に走査する。
3. 各 i について、j を i から文字列の末尾まで進めながら、s[j] が 'R' なら cnt を +1、そうでなければ -1 する。
4. j − i > 0 かつ cnt == 0 になった時点で、その範囲が 1 つのバランス文字列となるため、ans を +1 し、i を j に更新して内側のループを抜ける。
5. 最終的な ans を返す。

C++ 実装例

それでは、実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int balancedStringSplit(string s) {
        int cnt = 0;
        int ans = 0;
        for (int i = 0; i < s.size(); i++) {
            cnt = 0;
            for (int j = i; j < s.size(); j++) {
                if (s[j] == 'R') cnt++;
                else cnt--;
                if (j - i > 0 && cnt == 0) {
                    ans++;
                    i = j;
                    break;
                }
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    cout << ob.balancedStringSplit("RLLLLRRRLR");
}

入力と出力

入力：

"RLLLLRRRLR"

出力：

3

"RLLLLRRRLR" は "RL"、"LLRR"、"LR" という3つのバランス文字列に分割できます。

計算量の改善：貪欲法で O(n) に

上記の実装は二重ループを使用するため、時間計算量は O(n²) になります。しかし、入力文字列全体がバランスしていることが保証されているため、よりシンプルな貪欲法（グリーディ法）によって O(n) まで高速化できます。

考え方は非常にシンプルで、左から 1 文字ずつ読みながらカウンタを増減させ、カウンタが 0 に戻るたびにそこで区切るだけです。

class Solution {
public:
    int balancedStringSplit(string s) {
        int cnt = 0, ans = 0;
        for (char c : s) {
            if (c == 'R') cnt++;
            else cnt--;
            if (cnt == 0) ans++;
        }
        return ans;
    }
};

この方法が最適である理由は、カウンタが 0 になった瞬間に必ず区切ることで、残りの部分に対しても同じ戦略を繰り返し適用できるからです。それより早い地点ではバランスが崩れているため切ることができず、遅い地点で切ると分割数が減ってしまいます。

まとめ

• バランス文字列とは、'L' と 'R' が同数含まれる文字列のこと。
• 累積カウントが 0 に戻るたびに区切る貪欲法が有効。
• 時間計算量 O(n)、空間計算量 O(1) で効率的に解ける。