Rikka with String
Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 512000/512000 K (Java/Others)Total Submission(s): 5 Accepted Submission(s): 0
Problem Description
This is the last problem of this contest, so Rikka doesn't want to add a lengthy background to it. Let us make all the things simple and clear.
You have a string $s$ of length $n$ which only contains lowercase English letters from a to l (There are $12$ possible letters). You can choose a permutation of these $12$ letters $p_a,p_b,...,p_l$ and then you can get a string $t = p_{s_1}p_{s_2}...p_{s_n}$. Your task is to check whether the $i$th suffix (the substring $s[i,n]$) can become the largest suffix in lexicographic order after this modification.
You have a string $s$ of length $n$ which only contains lowercase English letters from a to l (There are $12$ possible letters). You can choose a permutation of these $12$ letters $p_a,p_b,...,p_l$ and then you can get a string $t = p_{s_1}p_{s_2}...p_{s_n}$. Your task is to check whether the $i$th suffix (the substring $s[i,n]$) can become the largest suffix in lexicographic order after this modification.
Input
The first line contains a single number $t(1 \leq t \leq 10^3)$, the number of testcases.
For each testcase, the first line contains a string $s(1 \leq |s| \leq 10^5)$.
The input guarantees that there are at most $15$ testcases with $|s| > 10^3$.
For each testcase, the first line contains a string $s(1 \leq |s| \leq 10^5)$.
The input guarantees that there are at most $15$ testcases with $|s| > 10^3$.
Output
For each testcase, output a single line with a $01$ string of length $|s|$. If the $i$th suffix can become the largest one, the $i$th position should be $1$. Otherwise, it should be $0$.
Sample Input
3 abaab abcdefghijkllkjihgfedcba aabbcccbaabcca
Sample Output
01100 111111111111011111111110 10101000100000