codeforces-scrape

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

1675E.md (1859B)


      1 Source: https://codeforces.com/problemset/problem/1675/E
      2 
      3 E. Replace With the Previous, Minimize
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 You are given a string $s$ of lowercase Latin letters.
     22 
     23 The following operation can be used:
     24 
     25 * 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'.
     26 
     27 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.
     28 
     29 The string $a=a_1a_2 \dots a_n$ is lexicographically smaller than the string $b = b_1b_2 \dots b_n$ if there exists an index $k$ ($1 \le k \le n$) such that $a_1=b_1$, $a_2=b_2$, ..., $a_{k-1}=b_{k-1}$, but $a_k \lt b_k$.
     30 
     31 Input
     32 
     33 The first line contains a single integer $t$ ($1 \le t \le 10^4$) —the number of test cases in the test.
     34 
     35 This is followed by descriptions of the test cases.
     36 
     37 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $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$.
     38 
     39 The second line of each test case contains a string $s$ of length $n$ consisting of lowercase Latin letters.
     40 
     41 It is guaranteed that the sum $n$ over all test cases does not exceed $2 \cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, output the lexicographically minimal string that can be obtained from the string $s$ by performing no more than $k$ operations.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 4
     53 
     54 3 2
     55 
     56 cba
     57 
     58 4 5
     59 
     60 fgde
     61 
     62 7 5
     63 
     64 gndcafb
     65 
     66 4 19
     67 
     68 ekyv
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 aaa
     75 agaa
     76 bnbbabb
     77 aapp
     78 ```