codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.