Longest Valid Parentheses

Q: Longest Valid Parentheses の時間計算量はどれくらいですか？

スタックを使う方法も2パスのカウンターを使う方法も、各文字を一定回数読み取るため、実行時間は O(n) です。スタックは、 ( だけで構成された文字列など、最悪の場合は O(n) のメモリを必要としますが、カウンターは O(1) です。すべての開始位置を試す方法は O(n²) です。

Q: Longest Valid Parentheses に対する動的計画法の解法はありますか？

はい。 end[i] を、インデックス i で終わる最長の正しい形式の部分文字列の長さとします。 s[i] が ( の場合は0です。 s[i-1] が ( なら、 end[i] = end[i-2] + 2 です。 ) の場合は、 j = i - end[i-1] - 1 、つまり i-1 で終わる連続部分の直前の文字を確認します。 s[j] が ( なら、その文字で連続部分を囲むことができ、 end[i] = end[i-1] + 2 + end[j-1] となります。最後の項は、左側で隣接する連続部分をつなげます。答えは end[i] の最大値で、時間計算量とメモリ計算量は O(n) です。

Q: なぜカウンターを使った1回の走査だけでは不十分なのでしょうか？

左から右への走査では、 ) の数が ( の数を上回ったときだけリセットされます。閉じられない余分な ( があると、文字列の残りの部分で数の差が保たれるため、走査中に数が一致することはありません。 (() では、開き括弧が2個、閉じ括弧が1個の状態で終わり、何も見つかりません。右から左へ読むと、最初の走査における余分な ) と同じように、余分な ( を扱います。そのため、2回の走査を合わせると、すべての連続部分を網羅できます。

むずかしいスタック動的計画法

+10

(と)だけで構成された文字列sが与えられます。正しい括弧の並びになっている最長の部分文字列（連続する文字の並び）を見つけてください。その部分文字列内のすべての(が後ろにある)で閉じられ、(()())のように括弧が正しく入れ子になっている必要があります。その部分文字列の長さを返してください。()すら含まれていない場合は0を返します。

関数

longestValidParentheses(s: string) → integer

sstring: ( と ) の文字列
戻り値integer: 最も長い整形式の部分文字列の長さ。存在しない場合は 0

制約

1 ≤ s.length ≤ 6 × 10⁴
sのすべての文字は(または)です。

例

入力: s = "()(())"
出力: 6
説明: 文字列全体は正しい形式です。()の後に(())が続いています。正しい形式の部分を2つ並べると、正しい形式の部分が1つできるので、答えは6文字すべてです。

入力: s = "())((())"
出力: 4
説明: インデックス2の)には対応する括弧がないため、それをまたいで答えを作ることはできず、インデックス3の(は閉じられないままです。最長の部分文字列はインデックス4から7までの(())で、長さは4です。これは先頭の()より長いです。

入力: s = "))(("
出力: 0
説明: 両方の ) が両方の ( より前に来るため、閉じられる ( はありません。正しい形式の部分文字列は存在せず、答えは 0 です。

提出時に隠しテスト+21件

発展問題

最長の整形式部分文字列がどこから始まるかも報告できますか。同じ長さの部分文字列が複数ある場合は、最も左にあるものを選んでください。

ヒント

1つずつ開いてください。開くたびに少しずつ答えに近づきます。

3個中0個を表示

解説

1つの文字列を確認するよりも難しくなる要因は2つあります。正しい形式の部分は隣り合うと結合するため、()と(())が隣接している場合、長さ6の1つの連続部分として数えます。また、())(())の)のような余分な文字が1つあると、文字列が分断され、その文字をまたぐ答えはありません。すべての開始位置を調べるとO(n²)のコストがかかります。解決策は、現在の連続部分がどこから始まったかを記録することです。最下部に基準位置のマーカーを置いたインデックスのスタックを使えば1回の走査で処理でき、単純なカウンターだけで2回走査すれば、スタックをまったく使わずに済みます。

すべての開始位置から部分文字列を伸ばす

正しいが、最大のテストでは終わらない

考え方

部分文字列を左から右へ読み、(で残高を1増やし、)で1減らします。残高が一度も0未満にならず、最後に0になるとき、その部分文字列は正しい括弧列です。0未満になるということは、閉じる対象がないのに)が現れたことを意味します。

そこで、開始位置を固定して右へ進み、1文字ずつ残高を更新します。残高が0に戻るたびに、開始位置からここまでの範囲は正しい括弧列なので、その長さを記録します。残高が0未満になった時点で終了します。その)は、この開始位置からのより長い範囲でも対応する開き括弧がないままです。正しい部分文字列には必ず開始位置があり、その開始位置についてすべての終端位置を試すため、見落としはありません。

問題は計算量です。59998個の(の後に()が続く文字列では、残高が0未満にならないため、どの開始位置からも末尾まで走査します。n = 6 × 10^4の場合、約 n²/2 = 1.8 × 10^9 回の処理になります。大きなテストケースはこのような形で作られています。（部分文字列を伸ばすのではなく、毎回最初から調べると、さらに遅くなり、O(n³)になります。）

アルゴリズム

bestを0に設定します。
各startについて、balanceを0に設定し、startから最後の文字までendを進めます。
(の場合は1を加算し、)の場合は1を減算します。
balanceが0未満なら、このstartの処理を停止します。0なら、長さend - start + 1でbestを更新します。
bestを返します。

def longestValidParentheses(s):
    best = 0
    for start in range(len(s)):
        balance = 0
        for end in range(start, len(s)):
            balance += 1 if s[end] == "(" else -1
            if balance < 0:
                # A ')' without a partner: no longer run starts here
                break
            if balance == 0:
                best = max(best, end - start + 1)
    return best

基準マーカー付きのインデックスのスタック

考え方

スタックを使って括弧の対応を調べる方法はおなじみです。各(をプッシュし、)ごとに1つポップします。ここでは長さも必要なので、インデックスをプッシュし、スタックの底にもう1つインデックスを保持します。これは基準位置、つまり現在の連続部分の直前の位置です。最初は何も読み込まれていないため、基準位置は-1です。

(の場合は、そのインデックスをプッシュします。)の場合はポップします。ここで2つのことが起こりえます。スタックが空になった場合は、基準位置をポップしたということなので、この)に対応する括弧はありません。整形式の部分文字列にこれを含めることはできず、これが新しい基準位置になります。そのインデックスをプッシュします。そうでない場合、スタックの先頭に残ったインデックスは、iで終わる連続部分の直前の最後の文字を指しています。まだ閉じられていない(か、基準位置のどちらかです。その位置の次からiまでが対応の取れた部分であり、連続部分はそれより左には伸びないため、長さはi - topです。

例として())((())を見てみましょう。

i = 0、(：0をプッシュします。スタックは[-1, 0]です。
i = 1、)：0をポップします。先頭は-1なので、連続部分の長さは1 - (-1) = 2です。
i = 2、)：-1をポップするとスタックが空になります。この)に対応する括弧はないため、新しい基準位置として2をプッシュします。スタックは[2]です。
i = 3, 4, 5、3つの(：それらをプッシュします。スタックは[2, 3, 4, 5]です。
i = 6、)：5をポップします。先頭は4なので、連続部分の長さは6 - 4 = 2です。
i = 7、)：4をポップします。先頭は3なので、連続部分の長さは7 - 3 = 4となり、これが答えです。

基準位置があることで、隣接する部分をつなげて数えられます。()(())では、最初のペアの長さは1 - (-1) = 2です。最後の)はインデックス2をポップし、再び先頭に-1があるため、長さは5 - (-1) = 6となります。対応する(から長さを測ると4になり、前の()を見落としてしまいます。各インデックスは最大1回ずつプッシュおよびポップされるため、この走査はO(n)で、スタックには最大n+1個のインデックスが入ります。

アルゴリズム

-1 を保持するスタックを用意し、best を 0 に設定します。
各インデックス i について、s[i] が ( の場合は i をプッシュします。
) の場合は、1 回ポップします。
スタックが空になった場合は、新しい基準として i をプッシュします。そうでなければ、i - top を使って best を更新します。
best を返します。

def longestValidParentheses(s):
    # The bottom of the stack is the index just before the current run
    stack = [-1]
    best = 0
    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                # This ')' has no partner: it becomes the new base
                stack.append(i)
            else:
                best = max(best, i - stack[-1])
    return best

開きと閉じを2回に分けて数える

考え方

スタックが教えてくれるのは、現在の連続部分がどこから始まったかだけです。2つのカウンターでも同じことができます。左から右へ進み、最後にリセットしてからのopensとclosesを数えます。両者が等しければ、リセット以降の部分はすべて正しく対応しており、長さは2 × closesです。closesが先行したら、)に対応する相手がありません。これはスタックが基準を失ったのと同じ瞬間なので、両方のカウンターを0にリセットします。

1回の走査では不十分です。一度も閉じない(があると、opensがずっと先行し、カウントが再び等しくなることはありません。(()では、左からの走査はopenが2つ、closeが1つの状態で終わり、何も報告しませんが、すぐそこに()があります。そこで、役割を入れ替えて、右から左へ2回目の走査をします。opensが先行したらリセットします。逆向きに読むと、(()はまずclose、次にopen（等しくなるので長さは2）、その次のopenでリセットとなります。答えは2回の走査で得た値の大きいほうです。

2回の走査ですべての連続部分を見つけられる理由：最長の連続部分は、決して対応づけられない文字、または文字列の端によって区切られています。左側の境界が余分な)または文字列の先頭なら、左からの走査はその連続部分が始まる位置でリセットされ、終わる位置でカウントが等しくなるのを検出します。左側の境界が余分な(なら、右側の境界が)になることはありません。その)が余分な(を閉じてしまい、連続部分がもっと長くなるからです。したがって、右側の境界は余分な(または文字列の末尾となり、右からの走査が同じようにその連続部分を見つけます。各走査では2つの整数を使って文字列を1回読み取るため、時間計算量はO(n)、追加のメモリはO(1)です。

アルゴリズム

best を 0 に設定し、opens と closes を 0 に設定します。
左から右へ進み、各文字を数えます。カウントが等しくなったら、best を 2 × closes で更新します。closes の方が大きくなったら、両方を 0 にリセットします。
両方のカウンターをリセットしてから、同じ方法で右から左へ進みます。ただし、opens の方が大きくなったらリセットします。
best を返します。

def longestValidParentheses(s):
    best = 0

    # Left to right: more ')' than '(' ends every run that started earlier
    opens = closes = 0
    for ch in s:
        if ch == "(":
            opens += 1
        else:
            closes += 1
        if opens == closes:
            best = max(best, 2 * closes)
        elif closes > opens:
            opens = closes = 0

    # Right to left: catches the runs that an unmatched '(' hid from the first pass
    opens = closes = 0
    for ch in reversed(s):
        if ch == "(":
            opens += 1
        else:
            closes += 1
        if opens == closes:
            best = max(best, 2 * opens)
        elif opens > closes:
            opens = closes = 0

    return best

落とし穴と境界ケース

多くの誤答は、正しいペアを間違った位置で数えたり、連続部分の開始位置を見失ったりしています。

文字列全体で一致するペアを数える。())((())には3組のペアがありますが、すべてが隣り合っているわけではないため、答えは6ではなく4です。
一致する(から連続部分の長さを測る。()(())では、最後の)はインデックス2にある(と一致するため、長さは4となり、その前にある()を見落とします。ポップ後にスタックに残ったインデックスから測ります。
空のスタックから始める。すると())の最初の)は長さを測る基準がなく、一致しない)が空のスタックからポップしようとします。基準となる-1で、この両方を解決できます。
カウンターを一方向だけで動かす。(()は左から右では0を返し、())は右から左では0を返しますが、どちらも答えは2です。
カウンターが等しいときにリセットする。()()のように、カウントが等しい場合も連続部分はまだ伸びる可能性があります。リセットするのは、片方の数がもう片方を上回ったときだけです。
LuaとRでは位置は1から始まるので、最初の基準値は-1ではなく0です。

よくある質問4

Longest Valid Parentheses の時間計算量はどれくらいですか？

スタックを使う方法も2パスのカウンターを使う方法も、各文字を一定回数読み取るため、実行時間は O(n) です。スタックは、( だけで構成された文字列など、最悪の場合は O(n) のメモリを必要としますが、カウンターは O(1) です。すべての開始位置を試す方法は O(n²) です。

スタックはなぜ -1 から始まるのですか？

連続部分の長さは、現在のインデックスから連続部分の直前のインデックスを引いた値です。インデックス 0 から始まる連続部分の場合、その直前のインデックスは -1、つまり文字列の1つ前です。最初に -1 をプッシュしておくと、一致する ) が長さを測るときにスタックが空になることはなく、一致しない ) がそれをポップすると、その ) が新しい基準になります。

Longest Valid Parentheses に対する動的計画法の解法はありますか？

はい。end[i]を、インデックスiで終わる最長の正しい形式の部分文字列の長さとします。s[i]が(の場合は0です。s[i-1]が(なら、end[i] = end[i-2] + 2です。)の場合は、j = i - end[i-1] - 1、つまりi-1で終わる連続部分の直前の文字を確認します。s[j]が(なら、その文字で連続部分を囲むことができ、end[i] = end[i-1] + 2 + end[j-1]となります。最後の項は、左側で隣接する連続部分をつなげます。答えはend[i]の最大値で、時間計算量とメモリ計算量はO(n)です。

なぜカウンターを使った1回の走査だけでは不十分なのでしょうか？

左から右への走査では、) の数が ( の数を上回ったときだけリセットされます。閉じられない余分な ( があると、文字列の残りの部分で数の差が保たれるため、走査中に数が一致することはありません。(() では、開き括弧が2個、閉じ括弧が1個の状態で終わり、何も見つかりません。右から左へ読むと、最初の走査における余分な ) と同じように、余分な ( を扱います。そのため、2回の走査を合わせると、すべての連続部分を網羅できます。

Python

def longestValidParentheses(s):
    # ここにコードを書いてください

テストケース

ケース1

ケース2

ケース3

入力

s = "()(())"

期待値

Longest Valid Parentheses

関数

制約

例

ヒント

解説

すべての開始位置から部分文字列を伸ばす

基準マーカー付きのインデックスのスタック

開きと閉じを2回に分けて数える

落とし穴と境界ケース

よくある質問4

似た問題