|
||||||||||
Rikka with StringTime Limit: 12000/6000 MS (Java/Others) Memory Limit: 512000/512000 K (Java/Others)Total Submission(s): 102 Accepted Submission(s): 4 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. 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$. 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
Sample Output
Source | ||||||||||
|