C++で隣接文字の交換・削除によって作れるバランス文字列の最大長を求める方法

( ) { } [ ] の6種類の括弧文字のみで構成された文字列が与えられたとき、隣接する文字の交換または文字の削除を行うことで得られる「バランスの取れた文字列」の最大の長さを求めるのが本記事のテーマです。

隣接する2文字を比較し、互いに対応関係にあるペアであれば交換が可能です。例えば }{、)(、][ は順序を入れ替えられますが、{{ や ))、[[ のように同じ種類の文字が並んでいる場合は交換できません。

さらに、どの文字ともペアを組めない孤立した文字は削除することが許されます。例えば "{{}][" の場合、先頭の { を削除すれば、長さ4のバランス文字列が残ります。

入力例と出力例

例1

入力: str[] = " {{{}}{]]][()" (長さ12)

出力: バランス文字列の最大長 = 8

解説:

• str[0] と str[1] は交換できないため str[0] を削除 → "{{}}{]]][()"
• 次に str[1] と str[2] も交換できないため削除 → "{}}{]]][()"
• {} はバランス成立。}{ は交換可能。
• 連続する ]] を2つ削除し、][ は交換して [] に。() もバランス成立。

最終的な文字列は {}{}[]() となり、長さは 8 です。

例2

入力: str[] = "(((((()" (長さ7)

出力: バランス文字列の最大長 = 2

解説: バランスが取れているのは str[5] と str[6] の () 部分だけなので、それ以外をすべて削除します。最終文字列は () で、長さは 2 です。

アルゴリズムの考え方

1. 文字配列 str[] に元の文字列を格納し、整数変数 len でその長さを保持します。
2. 関数 maxBalancedStr(char str[], int len) が文字列とその長さを受け取り、バランス文字列の最大長を返します。
3. 変数 count を用意し、結果となる長さを格納します(初期値は0)。
4. 文字列を先頭から走査し、隣接する2文字がすでにバランスしているか、または交換によってバランスできるペアであるかを判定します。該当すれば count に2を加算します。
5. ()/)(、{}/}{、[]/][ のようなペアが見つかった場合は i を追加的にインクリメントし、次の未処理の文字へ進みます。
6. 走査が完了した時点の count が求める最大長となります。
7. count を結果として返します。

C++による実装例

// アプローチのC++実装
#include <bits/stdc++.h>
using namespace std;

// 最長のバランス文字列の長さを返す関数
int maxBalancedStr(char str[20], int len){
    int count = 0;
    // 文字列を走査
    for (int i = 0; i < len; i++) {
        // 括弧の種類を判定し、対応するペアならカウントを加算
        if ((str[i]=='(' && str[i+1]==')') || (str[i]==')' && str[i+1]=='(')) {
            count += 2; ++i;
        }
        else if ((str[i]=='{' && str[i+1]=='}') || (str[i]=='}' && str[i+1]=='{')) {
            count += 2; ++i;
        }
        else if ((str[i]=='[' && str[i+1]==']') || (str[i]==']' && str[i+1]=='[')) {
            count += 2; ++i;
        }
    }
    return count;
}

// 動作確認用コード
int main(){
    char str[] = ")([]]((";
    int length = 7;
    cout << maxBalancedStr(str, length);
    return 0;
}

出力

4

まとめ

本手法では、文字列を一度だけ走査しながら隣接ペアの一致・交換可能性をチェックするため、計算量は O(n)、追加のメモリ使用量は O(1) で済みます。括弧の種類ごとに条件分岐を用意するシンプルな実装で、交換と削除の操作を前提としたバランス文字列の最大長を効率的に求められます。