Pythonで有効な括弧列を作るために必要な最小限の括弧削除を求めるプログラム

文字列 s には、括弧「(」「)」と小文字の英字が含まれているとします。この文字列から、任意の位置にある括弧「(」または「)」を最小限だけ削除し、結果として得られる括弧列を有効な状態にします。そして最終的に、有効な文字列を1つ返す必要があります。

ここで、括弧列が「有効」とみなされるのは、以下の条件のいずれかを満たす場合です。

• 文字列が空であるか、小文字の英字のみを含む場合
• 文字列が AB(A と B を連結した形)と表せる場合。ただし A と B はどちらも有効な文字列
• 文字列が (A) の形式で表せる場合。ただし A は有効な文字列

たとえば、入力が s = "m)n(o)p" の場合、対応する相手のいない「)」を取り除けばよいので、出力は "mn(o)p" となります。

解法のアプローチ:スタックを活用

この問題は、スタックを使うことで効率的に解けます。基本的な考え方は次の通りです。

• 「(」が出現したら、その位置(インデックス)をスタックにプッシュして記録しておく
• 「)」が出現したとき、スタックが空であれば対応する「(」が存在しない「余分な閉じ括弧」なので、そのインデックスを削除候補セット(indexes)に追加する。スタックに要素があればポップしてペア成立とみなす
• 走査が終わった時点でスタックに残っているインデックスは、対応する「)」を持たない「余分な開き括弧」なので、これらも indexes に追加する
• 最後に、indexes に含まれないインデックスの文字だけを順に連結した文字列を返せばよい

実装例(Python)

それでは、実際のコードを見ていきましょう。

def solve(s):
    stack = []
    indexes = set()
    i = 0

    for c in s:
        if c == '(':
            stack.append(i)
        elif c == ')':
            if len(stack) == 0:
                indexes.add(i)
            else:
                stack.pop()
        i += 1

    ret = ''
    indexes = indexes.union(stack)
    for i in range(len(s)):
        if i not in indexes:
            ret += s[i]

    return ret

s = "m)n(o)p"
print(solve(s))

入力

"m)n(o)p"

出力

mn(o)p

計算量の評価

このアルゴリズムの時間計算量は O(n)、空間計算量も O(n) です(n は文字列の長さ)。文字列を一度だけ走査し、スタックへの push / pop はすべて定数時間で行えるため、非常に効率的な解法といえます。また、削除する括弧の数が理論上の最小値になっていることも保証されます。