Replace With the Previous, Minimize solution codeforces – You are given a string 𝑠s of lowercase Latin letters.
The following operation can be used:
- select one character (from ‘a‘ to ‘z‘) that occurs at least once in the string. And replace all such characters in the string with the previous one in alphabetical order on the loop. For example, replace all ‘c‘ with ‘b‘ or replace all ‘a‘ with ‘z‘.
[Solution] Replace With the Previous, Minimize solution codeforces
And you are given the integer 𝑘k — the maximum number of operations that can be performed. Find the minimum lexicographically possible string that can be obtained by performing no more than 𝑘k operations.
The string 𝑎=𝑎1𝑎2…𝑎𝑛a=a1a2…an is lexicographically smaller than the string 𝑏=𝑏1𝑏2…𝑏𝑛b=b1b2…bn if there exists an index 𝑘k (1≤𝑘≤𝑛1≤k≤n) such that 𝑎1=𝑏1a1=b1, 𝑎2=𝑏2a2=b2, …, 𝑎𝑘−1=𝑏𝑘−1ak−1=bk−1, but 𝑎𝑘<𝑏𝑘ak<bk.
The first line contains a single integer 𝑡t (1≤𝑡≤1041≤t≤104) —the number of test cases in the test.
This is followed by descriptions of the test cases.
The first line of each test case contains two integers 𝑛n and 𝑘k (1≤𝑛≤2⋅1051≤n≤2⋅105, 1≤𝑘≤1091≤k≤109) — the size of the string 𝑠s and the maximum number of operations that can be performed on the string 𝑠s.
The second line of each test case contains a string 𝑠s of length 𝑛n consisting of lowercase Latin letters.
It is guaranteed that the sum 𝑛n over all test cases does not exceed 2⋅1052⋅105.
[Solution] Replace With the Previous, Minimize solution codeforces
For each test case, output the lexicographically minimal string that can be obtained from the string 𝑠s by performing no more than 𝑘k operations.
4 3 2 cba 4 5 fgde 7 5 gndcafb 4 19 ekyv
aaa agaa bnbbabb aapp