Pythonで括弧文字列のバランスを取るための最小挿入数を求めるプログラム

問題の概要

「(」と「)」から構成される文字列 s が与えられます。この問題では、括弧文字列がバランスしている状態を次のように定義します。

• すべての左括弧「(」に対して、対応する2つの連続した右括弧「))」が存在すること
• 左括弧「(」は、必ず対応する「))」より前に現れること

たとえば「())」や「())(())))」はバランスしていますが、「)()」や「()))」はバランスしていません。このような文字列が与えられたとき、左括弧または右括弧を挿入して文字列全体をバランスさせるために必要な最小の挿入回数を求めます。

入力例と考え方

たとえば入力が s = "(())))))" の場合、出力は 1 になります。文字列を分解すると「(())」「))」「))」と見なせます。「(())」はすでにバランスしており、次の「))」は既存のもう1つの左括弧と対応付けられますが、最後の「))」に対応する左括弧がありません。そこで左括弧を1つ挿入すれば、文字列はバランスします。

解法のアルゴリズム

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

• o := 0（未対応の左括弧の数）、n := 文字列 s の長さとする
• ret := 0（必要な挿入回数）、i := 0 とする
• i < n の間、次の処理を繰り返す。
  • s[i] が「(」の場合：o を 1 増やす
  • それ以外の場合：
    • i + 1 < n かつ s[i + 1] が「)」のとき（連続した「))」）：o が 0 なら ret を 1 増やし（左括弧が不足）、そうでなければ o を 1 減らす。その後、i をさらに 1 増やして「))」をまとめて消費する
    • そうでないとき（右括弧が単独で現れた場合）：ret を 1 増やし（右括弧を補う）、o が 0 ならさらに ret を 1 増やし（左括弧も併せて挿入）、そうでなければ o を 1 減らす
• 最後に ret + 2 * o を返す（余った左括弧1つごとに「))」2文字の挿入が必要なため）

実装例

理解を深めるために、以下のPython実装を見てみましょう。

def solve(s):
    o = 0
    n = len(s)
    ret = 0
    i = 0
    while i < n:
        if s[i] == '(':
            o += 1
        else:
            if i + 1 < n and s[i + 1] == ')':
                if not o:
                    ret += 1
                else:
                    o -= 1
                    i += 1
            else:
                ret += 1
                if not o:
                    ret += 1
                else:
                    o -= 1
        i += 1
    return ret + 2 * o

s = "(())))))"
print(solve(s))

入力

"(())))))"

出力

1

計算量

• 時間計算量：O(n) ― 文字列を先頭から一度だけ走査します。
• 空間計算量：O(1) ― カウンタ変数のみを使用し、追加のデータ構造は不要です。