1905C.md (2299B)
1 Source: https://codeforces.com/problemset/problem/1905/C 2 3 C. Largest Subsequence 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Given is a string $s$ of length $n$. In one operation you can select the lexicographically largest$^\dagger$ subsequence of string $s$ and cyclic shift it to the right$^\ddagger$. 22 23 Your task is to calculate the minimum number of operations it would take for $s$ to become sorted, or report that it never reaches a sorted state. 24 25 $^\dagger$A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds: 26 27 * $a$ is a prefix of $b$, but $a \ne b$; 28 * In the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$. 29 30 $^\ddagger$By cyclic shifting the string $t_1t_2\ldots t_m$ to the right, we get the string $t_mt_1\ldots t_{m-1}$. 31 32 Input 33 34 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows. 35 36 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the string $s$. 37 38 The second line of each test case contains a single string $s$ of length $n$, consisting of lowercase English letters. 39 40 It is guaranteed that sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 41 42 Output 43 44 For each test case, output a single integer — the minimum number of operations required to make $s$ sorted, or $-1$ if it's impossible. 45 46 Example 47 48 Input 49 50 ``` 51 6 52 53 5 54 55 aaabc 56 57 3 58 59 acb 60 61 3 62 63 bac 64 65 4 66 67 zbca 68 69 15 70 71 czddeneeeemigec 72 73 13 74 75 cdefmopqsvxzz 76 ``` 77 78 Output 79 80 ``` 81 0 82 1 83 -1 84 2 85 6 86 0 87 ``` 88 89 Note 90 91 In the first test case, the string $s$ is already sorted, so we need no operations. 92 93 In the second test case, doing one operation, we will select cb and cyclic shift it. The string $s$ is now abc which is sorted. 94 95 In the third test case, $s$ cannot be sorted. 96 97 In the fourth test case we will perform the following operations: 98 99 * The lexicographically largest subsequence is zca. Then $s$ becomes abzc. 100 * The lexicographically largest subsequence is zc. Then $s$ becomes abcz. The string becomes sorted. 101 102 Thus, we need $2$ operations.