[Solution] Replace With the Previous, Minimize solution codeforces

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.

Input

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𝑛21051≤n≤2⋅1051𝑘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 21052⋅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.

Example
input

Copy
4
3 2
cba
4 5
fgde
7 5
gndcafb
4 19
ekyv
output

Copy
aaa
agaa
bnbbabb
aapp

 

For Solution

Click here

Leave a Comment