Pythonで最長のバランス括弧部分列の長さを求めるプログラム

問題概要

文字列 s が与えられます。この文字列には括弧「(」と「)」が含まれており、その中からバランスの取れた（対応関係が成立している）括弧の部分列として最も長いものを見つけ、その長さを返すことが目標です。

たとえば、入力が s = "())(()(" の場合、出力は 4 になります。「(」と「)」を選び抜いて "()()" というバランスの取れた部分列を作れるためです。

解法のアプローチ

この問題は、文字列を後ろから走査することで線形時間で解けます。閉じ括弧を先に確保しておき、開き括弧が出てきたときに対を成立させるという発想です。手順は以下の通りです。

• 結果を格納する変数 res を 0 で初期化します。
• まだ対応する相手が見つかっていない閉じ括弧「)」の数を数える変数 close を 0 で初期化します。
• 文字列の末尾（インデックス n-1）から先頭に向かって 1 文字ずつ処理します。
• 現在の文字が「)」の場合：close を 1 増やします。
• 現在の文字が「(」で、かつ close > 0 の場合：ペアが成立するので close を 1 減らし、res に 2 を加算します。
• ループが完了したら、res を返します。

実装例（Python）

以下に実際の実装を示します。理解を深めるために参照してください。

class Solution:
    def solve(self, s):
        res = 0
        n = len(s)
        close = 0
        for i in range(n - 1, -1, -1):
            if s[i] == ")":
                close += 1
            else:
                if close > 0:
                    close -= 1
                    res += 2
        return res

ob = Solution()
s = "())(()("
print(ob.solve(s))

入力

"())(()("

出力

4

計算量の評価

このアルゴリズムは文字列を一度だけ走査するため、時間計算量は O(n)、使用する補助変数が定数個のみであることから空間計算量は O(1) となります。非常にシンプルかつ効率的な手法です。