Pythonで有効な括弧文字列を2つに分割し、最大ネスト深度を最小化する方法

問題の概要

文字列が「(」と「)」のみで構成され、かつ以下のいずれかの性質を満たすとき、その文字列は有効な括弧文字列(VPS: Valid Parentheses String)と呼ばれます。

• 空文字列である、または
• AB という形式で表せる(A と B はどちらも VPS)、または
• (A) という形式で表せる(A は VPS)

さらに、任意の VPS である S に対して、ネスト深度 depth(S) を次のように定義します。

• depth("") = 0
• depth(A + B) = max(depth(A), depth(B))(A と B は VPS)
• depth("(" + A + ")") = 1 + depth(A)(A は VPS)

求めるもの

VPS である seq が与えられたとき、これを互いに素な 2 つの部分列 A と B に分割します。A と B はどちらも VPS であり、len(A) + len(B) = len(seq) を満たす必要があります。このとき、max(depth(A), depth(B)) が最小になるように A と B を選択し、その選択結果を seq と同じ長さの答え配列として返します。

• seq[i] が A に属する場合:answer[i] = 0
• seq[i] が B に属する場合:answer[i] = 1

例えば、入力が "()(())()" の場合、出力は [1, 1, 1, 0, 1, 0, 1, 1] となります。

解法のアプローチ

この問題は貪欲法(Greedy)で効率的に解くことができます。手順は以下の通りです。

• n := seq の長さ、res := 長さ n の 0 で初期化された配列
• c1, c2 := 0, 0(それぞれグループ A と B の現在の深度を追跡)
• i を 0 から n-1 までループ:
  • seq[i] == '(' の場合:c1 < c2 なら c1 を 1 増やす。そうでなければ c2 を 1 増やし、res[i] = 1 とする
  • それ以外(')' の場合):c1 > c2 なら c1 を 1 減らす。そうでなければ c2 を 1 減らし、res[i] = 1 とする
• 最後に res を返す

このアルゴリズムのポイントは、開き括弧に出会うたびに現時点でより浅い方のグループへ割り当てることです。こうすることで、両グループの深度差を常に最小に保ち、結果として max(depth(A), depth(B)) を最小化できます。計算量は O(n)、空間計算量も O(n) です。

実装例

class Solution(object):
    def maxDepthAfterSplit(self, seq):
        n = len(seq)
        res = [0] * n
        c1, c2 = 0, 0
        for i in range(n):
            if seq[i] == '(':
                if c1 < c2:
                    c1 += 1
                else:
                    c2 += 1
                    res[i] = 1
            else:
                if c1 > c2:
                    c1 -= 1
                else:
                    c2 -= 1
                    res[i] = 1
        return res

ob = Solution()
print(ob.maxDepthAfterSplit("()(())()"))

入力

"()(())()"

出力

[1, 1, 1, 0, 1, 0, 1, 1]

まとめ

本記事では、有効な括弧文字列(VPS)を 2 つの部分列に分割し、最大ネスト深度を最小化する問題を取り上げました。カウンタ c1 と c2 で各グループの深度を管理しながら貪欲に割り当てることで、O(n) の計算量で最適解を得られます。括弧の対応関係を利用したシンプルなアルゴリズムなので、スタックや深さの概念を学ぶ練習問題としても最適です。