次のようなアルゴリズムを考えます。

整数 \(c\) を \(c = 0\) 、集合 \(X_0,X_1,X_2, \ldots X_{|S|}\) を空集合で初期化する。

\(i = 1,2, \ldots |S|\) についてこの順に以下の操作を行う。

• \(S_i = \) ( のとき、\(c\) の値を \(1\) 増やす。
• \(S_i = \) ) のとき、\(X_c\) を空にして \(c\) の値を \(1\) 減らす。
• \(S_i\) が英小文字のとき、\(X_c \gets X_c \cup \{S_i\}\) とする。ただし、 \(S_i \in \displaystyle \bigcup_{t} X_t\) ならば高橋君は気を失うと判定する。

以下、このアルゴリズムの正当性を示します。

\(S_i =\) ) で、\(j\) が \(S\) の \(j\) 番目から \(i\) 番目までの文字からなる文字列が良い文字列となる最大の整数とします。

このとき \(i\) に関する操作は 「\(c\) を \(i\) に関する操作を行う直前の値とし、（これは \(j\) に関する操作を行った直後の \(c\) の値に等しい）\(d \geq c\) を満たすすべての \(d\) について \(X_d\) を空にする」ことにあたりますが、実際には \(d > c\) のときは \(X_d\) は空集合です。

\(\displaystyle \bigcup_{t} X_t\) は高々 \(26\) 元集合なので、上のアルゴリズムは十分高速に動作し、以上よりこの問題を解くことができました。

実装例

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
	string s;
	cin >> s;
	int n = s.size();
	vector<vector<char>> v(n);
	vector<bool> used(256);
	int now = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == '(') now++;
		else if (s[i] == ')') {
			for (char c : v[now]) used[c] = false;
			v[now].clear();
			now--;
		}
		else {
			if (used[s[i]]) {
				cout << "No\n";
				return 0;
			}
			v[now].push_back(s[i]);
			used[s[i]] = true;
		}
	}
	cout << "Yes\n";
}