Consider the following algorithm.

Initialize an integer \(c\) with \(c = 0\) and each of the sets \(X_0,X_1,X_2, \ldots X_{|S|}\) with an empty set.

Perform the following operation for each \(i = 1,2, \ldots |S|\) in this order:

• If \(S_i = \) (, increment the value of \(c\) by \(1\).
• If \(S_i = \) (, empty \(X_c\) and decrement the value of \(c\) by \(1\).
• If \(S_i\) is a lowercase English letter, let \(X_c \gets X_c \cup \{S_i\}\). Here, if \(S_i \in \displaystyle \bigcup_{t} X_t\), determine that Takahashi faints.

Now we justify this algorithm.

Suppose that \(S_i =\) ) and \(j\) is the maximum integer such that the \(j\)-th through \(i\)-th characters of \(S\) forms a good string.

Then, the operation on \(i\) is equivalent to the following: “let \(c\) be the value right before when performing the operation on \(i\) (which is equal to the value of \(c\) right after when performing the operation on \(j\)), and empty \(X_d\) for all \(d\) such that \(d \geq c\). Actually, \(X_d\) is an empty set when \(d > c\).

Since \(\displaystyle \bigcup_{t} X_t\) is a set with at most \(26\) elements, the algorithm above works fast enough. Therefore, the problem has been solved.

Sample code

#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";
}