problem.txt (1963B)
1 C. Largest Subsequence 2 time limit per test1 second 3 memory limit per test256 megabytes 4 Given is a string s 5 of length n 6 . In one operation you can select the lexicographically largest† 7 subsequence of string s 8 and cyclic shift it to the right‡ 9 . 10 11 Your task is to calculate the minimum number of operations it would take for s 12 to become sorted, or report that it never reaches a sorted state. 13 14 † 15 A string a 16 is lexicographically smaller than a string b 17 if and only if one of the following holds: 18 19 a 20 is a prefix of b 21 , but a≠b 22 ; 23 In the first position where a 24 and b 25 differ, the string a 26 has a letter that appears earlier in the alphabet than the corresponding letter in b 27 . 28 ‡ 29 By cyclic shifting the string t1t2…tm 30 to the right, we get the string tmt1…tm−1 31 . 32 33 Input 34 Each test consists of multiple test cases. The first line contains a single integer t 35 (1≤t≤104 36 ) — the number of test cases. The description of the test cases follows. 37 38 The first line of each test case contains a single integer n 39 (1≤n≤2⋅105 40 ) — the length of the string s 41 . 42 43 The second line of each test case contains a single string s 44 of length n 45 , consisting of lowercase English letters. 46 47 It is guaranteed that sum of n 48 over all test cases does not exceed 2⋅105 49 . 50 51 --- 52 53 thoughts: 54 55 - string s of length n 56 - one op: 57 - select largest subsequence 58 - lexographically 59 - cyclic shift one right 60 - find min number of shifts to sort s 61 - or state it doesn't ever get sorted 62 63 --- 64 65 aaabc 66 67 (already sorted) 68 = 0 69 70 --- 71 72 acb 73 74 largest := cb 75 76 abc 77 78 = 1 79 80 --- 81 82 bac 83 84 largest = c 85 86 can't rotate that. 87 88 = -1 89 90 --- 91 92 zbca 93 94 largest = zca 95 96 1. find largest character 97 2. all subsequent characters are part of the largest subsequence unless there's a character to the right that's larger (suffix max) 98 - rotate that 99 - if in same state as seen before, return -1 100 - keep going until that's not true ig 101 102 abzc 103 104 abcz 105 106 = 2 107 108 109 --- 110 111 czddeneeeemigec 112 113 --- 114 115 cdefmopqsvxzz 116