시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
6 초 | 512 MB | 0 | 0 | 0 | 0.000% |
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_{\texttt{a}}, p_{\texttt{b}}, \ldots, p_{\texttt{l}}$, and then consider the string $t = p_{s_1} p_{s_2} \ldots p_{s_n}$. Your task is to check for each $i$ from $1$ to $n$ whether the $i$-th suffix (the substring $t[i, n]$) can become the largest suffix of $t$ in lexicographical order after such modification.
The first line contains a single integer $t$ ($1 \leq t \leq 10^3$), the number of test cases.
Each test case is given on a separate line containing a string $s$ ($1 \leq |s| \leq 10^5$, the string contains only lowercase English letters from "a
" to "l
").
It is guaranteed that there are at most $15$ test cases with $|s| > 10^3$.
For each test case, output a single line with a binary string of length $|s|$. If the $i$-th suffix can become the largest one, the $i$-th position must contain "1
". Otherwise, it must contain "0
".
3 abaab abcdefghijkllkjihgfedcba aabbcccbaabcca
01100 111111111111011111111110 10101000100000