CF1905C Largest Subsequence

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 $ . 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. $ ^\dagger $ A string $ a $ is lexicographically smaller than a string $ b $ if and only if one of the following holds: - $ a $ is a prefix of $ b $ , but $ a \ne b $ ; - 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 $ . $ ^\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} $ .

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. 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 $ . The second line of each test case contains a single string $ s $ of length $ n $ , consisting of lowercase English letters. It is guaranteed that sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output a single integer — the minimum number of operations required to make $ s $ sorted, or $ -1 $ if it's impossible.

In the first test case, the string $ s $ is already sorted, so we need no operations. 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. In the third test case, $ s $ cannot be sorted. In the fourth test case we will perform the following operations: - The lexicographically largest subsequence is zca. Then $ s $ becomes abzc. - The lexicographically largest subsequence is zc. Then $ s $ becomes abcz. The string becomes sorted. Thus, we need $ 2 $ operations.