Replace With the Previous, Minimize Codeforces Solution | Codeforces Problem Solution 2022

Replace With the Previous, Minimize Codeforces Solution | Codeforces Problem Solution 2022 

E. Replace With the Previous, Minimize

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 Click Below:- CLICK HERE

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=a_1{a}_2\dots a_n$ is lexicographically smaller than the string 𝑏=𝑏1𝑏2…𝑏𝑛$b=b_1{b}_2\dots b_n$ if there exists an index 𝑘$k$ (1≤𝑘≤𝑛$1\le k\le n$) such that 𝑎1=𝑏1$a_1=b_1$, 𝑎2=𝑏2$a_2=b_2$, ..., 𝑎𝑘−1=𝑏𝑘−1$a_{k-1}=b_{k-1}$, but 𝑎𝑘<𝑏𝑘$a_k<b_k$.

Input

The first line contains a single integer 𝑡$t$ (1≤𝑡≤104$1\le t\le {10}^4$) —the number of test cases in the test.

Food for Animals Codeforces Solution | Codeforces Problem Solution 2022 

Make It Increasing Codeforces Solution | Codeforces Problem Solution 2022 

Detective Task Codeforces Solution | Codeforces Problem Solution 2022 

Vertical Paths Codeforces Solution | Codeforces Problem Solution 2022 

Replace With the Previous, Minimize Codeforces Solution 

Vlad and Unfinished Business Codeforces Solution 

Sorting Pancakes Codeforces Solution 

This is followed by descriptions of the test cases.

The first line of each test case contains two integers 𝑛$n$ and 𝑘$k$ (1≤𝑛≤2⋅105$1\le n\le 2\cdot {10}^5$, 1≤𝑘≤109$1\le k\le {10}^9$) — 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⋅105$2\cdot {10}^5$.

Output

For each test case, output the lexicographically minimal string that can be obtained from the string 𝑠$s$ by performing no more than 𝑘$k$ operations.

Join Now for Solution:-