|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|서브태스크 참고 (추가 시간 없음)||1024 MB (추가 메모리 없음)||17||15||13||86.667%|
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 ≤ i < j ≤ L (1-based), the character at position i is smaller than the character at position j.
For example, the strings
ADF are strictly increasing, however the strings
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 ≤ i ≤ N, what is the length of the longest strictly increasing substring that ends at position ii.
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: y1 y2 ... yn, where x is the test case number (starting from 1) and yi is the length of the longest strictly increasing substring that ends at position i.
시간 제한: 20 초
시간 제한: 40 초
2 4 ABBC 6 ABACDA
Case #1: 1 2 1 2 Case #2: 1 2 1 2 3 1
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
In Sample Case #2, the longest strictly increasing substrings for each position are