文字列 \(X\) の長さを \(|X|\) と表します。

最終的な答えが操作手順によらないことから、前から順に貪欲に操作を行ってよいです。すなわち、直感的にいえば「先頭から順に見て、) を見つけるたびに、直前の ( までを削除する」としてよいです。これを正確に表現した次のような手順を考えます。

• \(S\) の先頭から順に次の処理を行う
  • いま注目している文字が ) でないなら何もしない
  • いま注目している文字が ) であるなら、いま注目している位置より前にある最も近い ( を探す
    • そのような ( が存在するならその ( からいま注目している ) までを削除する
    • 存在しないなら何もしない
• \(S\) を出力する

この手順では文字列の削除に (多くの言語では) \(\Theta(|S|)\) 時間かかるため、例えば \(S\) が ()()()... であった場合に、\(\Theta(N^2)\) 時間かかってしまいます。そこで、\(S\) を直接編集するのではなく、答えを格納する文字列を別に用意しておき、それを編集することを考えます。すなわち、次のような手順を考えます。

• 空の文字列 \(T\) を用意する。\(S\) の先頭から順に次の処理を行う
  • いま注目している文字 \(c\) が ) でないなら、\(c\) を \(T\) の末尾に追加する
  • いま注目している文字 \(c\) が ) であるなら、\(T\) の最も後ろにある ( を探す
    • そのような ( が存在するなら \(T\) のその ( 以降を全て削除する
    • 存在しないなら \(c\) を \(T\) の末尾に追加する
• \(T\) を出力する

この場合、削除する文字列が常に \(T\) の suffix であることから (多くの言語では) \(O(\text{削除する文字数})\) で削除処理が行なえます。しかしこの手順でも \(S\) が ))))))... などである場合などに「\(T\) の最も後ろにある ( を探す」に毎回 \(\Theta(|T|)\) 時間かかるため、全体で \(\Theta(N^2)\) 時間となります。これを改善するために「\(T\) に含まれる ( の位置」を全て覚えておくことにします。すなわち、次のような手順を考えます。

• 空の配列 \(A\) 、空の文字列 \(T\) を用意し、\(S\) の先頭から順に次の処理を行う
  • いま注目している文字 \(c\) が ( でも ) でもないなら、\(c\) を \(T\) の末尾に追加する
  • いま注目している文字 \(c\) が ( なら、\(c\) を \(T\) の末尾に追加し、その index を\(A\) の末尾に追加する
  • いま注目している文字 \(c\) が ) であるなら、\(A\) が空であるかどうか確認する
    • \(A\) が空でないなら、その末尾の要素を \(x\) とし、\(T\) の\(x\) 文字目以降を全て削除する。さらに、\(x\) を \(A\) から削除する
    • \(A\) が空なら、\(c\) を \(T\) の末尾に追加する
• \(T\) を出力する

こうすることで、「いま注目している位置より前にある最も近い ( を探す」ことが \(O(1)\) 時間でできるようになり、文字列の削除にかかる時間は合計で \(O(N)\) であることから、全体で \(O(N)\) 時間で解くことができました。

このように、処理全体のどこに時間がかかっているかを見極め、それを改善するためにはどうすればよいかを \(1\) ステップずつ考えることが、問題に取り組む上では重要です。

なお実際には、\(A\) を直接保持する必要はなく、( の個数だけ覚えておき、「\(1\) 個以上あるなら、\(T\) の末尾から遡って探す」とすることでも全体で \(O(N)\) 時間となります。

writer解(C)
writer解(C++)