C++で文字列内のバランス位置の数を求める方法

文字列が与えられたとき、その文字列を左右に分割した際に、左側と右側の両方に同じ種類の文字が含まれる分割位置(バランス位置)の数を求める問題について解説します。なお、文字の出現頻度は問われず、文字の種類が一致していればよい点に注意してください。

例えば、文字列が「ABAABA」の場合、バランス位置の数は 3 となります。具体的には、以下の3つの分割位置が該当します。

• AB | AABA
• ABA | ABA
• ABAA | BA

アルゴリズムの考え方

この問題は、以下のような効率的なアプローチで解くことができます。

1. まず文字列全体を走査し、すべての文字の出現回数を right[] 配列に記録します。
2. 次に、文字列を左から右へ走査します。各文字について、left[] 配列のカウントを1増やし、right[] 配列のカウントを1減らします。
3. 走査中の任意の時点で、「left[] 内で0以外の値を持つすべての文字が right[] でも0以外の値を持つ」かつ「その逆も成り立つ」場合、その位置はバランス位置であるため、結果を1増やします。

サンプルコード

#include <iostream>
#include <algorithm>
#define MAX_CHAR 256
using namespace std;
int countBalancePoints(string str) {
    int left[MAX_CHAR] = {0};
    int right[MAX_CHAR] = {0};
    for (int i=0; i<str.length(); i++)
    right[str[i]]++;
    int count = 0;
    for (int i=0; i < str.length() ; i++) {
        left[str[i]]++;
        right[str[i]]--;
        int j;
        for (j=0; j<MAX_CHAR; j++) {
            if ( (left[j] == 0 && right[j] != 0) || (left[j] != 0 && right[j] == 0))
            break;
        }
        if (j == MAX_CHAR)
            count++;
    }
    return count;
}
int main() {
    char str[] = "ABAABA";
    cout << "Number of balance points: " << countBalancePoints(str);
}

出力結果

Number of balance points: 3

計算量について

このアルゴリズムでは、文字列の走査に O(n)、各位置での文字種の一致チェックに O(256)(定数時間)を要するため、全体の時間計算量は O(n) となります。補助配列として left[] と right[] の2つの固定サイズ配列を使用するため、空間計算量は O(1) です。