この解法は公式解説と同一ですが、もう少し直感的に分かる解法を目指したものです。

今回の問題を、愚直にシミュレーションして解くことを考えます。

まず、問題文中に出てくる箱は高々一つのボールを入れるものなので、これは箱に入っているボールの集合 \(X\) を管理することで求められます。

シミュレーションを行うと、以下のように操作を行うことになります。

• \(S_i\) が(のとき、何もしない。
• \(S_i\) が英小文字の時、 \(X\) に既に \(S_i\) が含まれているならばNoを出力し、そうでないならば \(X\) に \(S_i\) を追加する。
• \(S_i\) が)の時、(を発見するまで文字を遡り、出てきた文字 \(S_j\) を全て \(X\) から削除する。 その後、対応する(…)を削除する。

このアルゴリズムの計算量は、どの文字についても最初に参照された時と削除される時の2回しか参照されないため \(O(|S|)\) となります。

ただ、削除処理を書くのは少し面倒に感じます。 そこで、削除を実質的に行ったように振舞う構造を考えます。

まず、集合のスタック \(Y\) を用意します。また、 \(Y_{\mathrm top}\) をスタックの一番上に入っている集合とします。

そして、以下の様に処理を行います。

• \(S_i\) が(のとき、 \(Y\) に空集合を追加する。
• \(S_i\) が英小文字の時、\(X\) に既に \(S_i\) が含まれているならばNoを出力し、そうでないならば \(X\) と \(Y_{\mathrm top}\) に \(S_i\) を追加する。
• \(S_i\) が)の時、 \(X\) から \(Y_{\mathrm top}\) に含まれる文字を取り除く。その後、 \(Y\) の先頭を除去する。

これは括弧列をスタックを用いて処理を行う(括弧列を根付き木とみなした時、DFSを用いて解くことに相当します)典型で、やっていることは前者のアルゴリズムと同じになります。

なお、この手法では \(26\) 元集合である性質を一切使っていないため、もし英小文字より多くの文字を扱うことになっても計算量はほぼ変わりません。