P16841 [GKS 2021 #B] Increasing Substring

Your friend John just came back from vacation, and he would like to share with you a new property that he learned about strings. John learned that a string $C$ of length $L$ consisting of uppercase English characters is strictly increasing if, for every pair of indices $i$ and $j$ such that $1 \le i < j \le L$ ($1$-based), the character at position $i$ is smaller than the character at position $j$. For example, the strings `ABC` and `ADF` are strictly increasing, however the strings `ACC` and `FDA` are not. Now that he taught you this new exciting property, John decided to challenge you: given a string $S$ of length $N$, you have to find out, for every position $1 \le i \le N$, what is the length of the longest strictly increasing substring that ends at position $i$.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case consists of two lines. The first line contains an integer $N$, representing the length of the string. The second line contains a string $S$ of length $N$, consisting of uppercase English characters.

For each test case, output one line containing `Case #x:` followed by $y_1\ y_2\ \ldots\ y_n$, where $x$ is the test case number (starting from $1$) and $y_i$ is the length of the longest strictly increasing substring that ends at position $i$.

In Sample Case $1$, the longest strictly increasing substring ending at position $1$ is `A`. The longest strictly increasing substrings ending at positions $2$, $3$, and $4$ are `AB`, `B`, and `BC`, respectively. In Sample Case $2$, the longest strictly increasing substrings for each position are `A`, `AB`, `A`, `AC`, `ACD`, and `A`. ### Limits $1 \le T \le 100$. **Test Set $1$** $1 \le N \le 100$. **Test Set $2$** $1 \le N \le 2 \times 10^5$.