Let \(\lvert S\rvert\) denote the length of a string \(S\), and \(+\) denote string concatenation.

Recursive definition of colorful bracket sequence

By definition of colorful bracket sequence, a colorful bracket sequence must have an even length. Obviously, only (), [], and <> are colorful bracket sequences. Moreover, bracket sequences of length \(N\) \((N\geq 4)\) satisfy the following properties:

• For a colorful bracket sequence \(S'\) of length \((N-2)\), the strings obtained by surrounding \(S'\) with (), [], and <> are all colorful bracket sequences. In other words, (+S’+), [+S’+], and <+S’+> are all colorful bracket sequences.
• For colorful bracket sequences \(S'\) and \(T'\) whose lengths sum to \(N\), the string obtained by concatenating \(S'\) and \(T'\) is a colorful bracket sequence. In other words, if \(\lvert S'\rvert+\lvert T'\rvert=N\), then \(S=S'+T'\) is a colorful bracket sequence.

Now we will prove that this is a recursive definition of colorful bracket sequence. In other words, we will show that any bracket sequence of length \(N\) can be written in one of the forms above.
For a colorful bracket sequence \(T\) of length \(N\), by definition there exists a sequence of operations that makes it an empty string. Then, the sequence contains an operation that removes the first character of \(T\); take the first such operation and consider the position of the other character that is removed by that operation.
If it is the \(N\)-th (last) character, it means the \(1\)-st and \(N\)-th characters can be removed at the same time, which implies the \(2\)-nd through \((N-1)\)-th characters are all removed by the operations. Thus, the string formed by the \(2\)-nd through \((N-1)\)-th characters of \(T\) is a colorful bracket string. Since the \(1\)-st and \(N\)-th are also removed, it satisfies the former property above.
Next, we consider the case where the \(k\)-th character is removed together, where \(2\leq k<N\). Then, for any integer \((i,j)\) with \(i\leq k<j\), the operation sequence never contains one that removes the \(i\)-th and \(j\)-th character simultaneously. This is because, as long as the \(k\)-th character remains, any characters before the \((k-1)\)-th and after the \((k+1)\)-th never become adjacent, while the \(k\)-th is also removed at the same time as the \(1\)-st, when any characters before the \(k\)-th no longer exist. Therefore, the \(k\)-th and prior characters and \((k+1)\)-th later characters can be considered separately. Hence, the substring formed by \(1\)-st through \(k\)-th characters of \(T\) and that from \((k+1)\)-th through \(N\)-th are both colorful bracket sequences. This applies to the second property of the recursive definition above.

Thus, it has been shown that the above is an appropriate recursive definition of a colorful bracket sequence.
Here, when we enumerate a colorful bracket sequence (like counting distinct sequences), we need to be aware that decomposition into colorful bracket sequences is not necessarily unique, though this time it does not matter because we just need to check if it is a colorful bracket sequence or not.

Solution

There are several ways to check if it is applicable. One is to use a data structure like a stack.

For the given string \(S\), perform the following operation for each \(i=1,2,\ldots,\lvert S\rvert\) in order.

• If the \(i\)-th character of \(S\) is one of (, [, and <, push it to (the top of) the stack.
• Otherwise, i.e. if the \(i\)-th character of \(S\) is one of ), ], and >, if the stack is empty, or the topmost element in the stack is not the corresponding opening parenthesis (e.g. [ for ]), then \(S\) is not a colorful bracket sequence. If it is, remove the topmost element of the stack.

If this process can be proceeded until the end, and the stack is empty at that point, then \(S\) is a colorful bracket sequence, and otherwise \(S\) is not.

To show the validity of this algorithm, it is sufficient to show that it terminates successfully with an empty stack if the given string is a colorful bracket sequence, and if it does, then the given string is a colorful bracket sequence.
For the former, it is obviously true for length \(2\), and those for length \(4\) or greater can also be shown inductively according to the recursive definition of colorful bracket sequence.
For the latter, if the procedure can be executed until the end, then one can construct an operation sequence consisting of, for each removal of a character from the front of the stack, an operation that removes that character and the character that was paired when removing it from the stack. Thus, \(S\) is a colorful bracket sequence. One can arrange the operations in a valid order so that removing a substring can be always possible by sorting the operations in descending order of the number of elements in the stack.

This procedure runs in \(O(\lvert S\rvert)\) time, which is fast enough.
Thus, the problem has been solved.

Sample code in C++:

#include <bits/stdc++.h>
using namespace std;

int main(void){
	int n;
	string s;
	stack<char> st;

	cin>>s;
	n=s.size();
	for(int i=0;i<n;i++){
		if((s[i]=='(')||(s[i]=='[')||(s[i]=='<'))st.push(s[i]);
		else{
			bool flag=false;
			if(st.empty()){
			  cout<<"No"<<endl;
				return 0;
			}
			if((s[i]==')')&&(st.top()!='('))flag=true;
			if((s[i]==']')&&(st.top()!='['))flag=true;
			if((s[i]=='>')&&(st.top()!='<'))flag=true;
			if(flag){
				cout<<"No"<<endl;
				return 0;
			}
			st.pop();
		}
	}
	if(st.empty())cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}