Replace With the Previous, Minimize (Codeforces 1675E)
Tags: Greedy, dsu

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'. 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 $$$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 < b_k$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) —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 \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$$$.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 \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.


Sample Inputs:
4
3 2
cba
4 5
fgde
7 5
gndcafb
4 19
ekyv

Sample Outputs:
aaa
agaa
bnbbabb
aapp

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
import math

def solve(n, k, a):
    m = {}
    maxi = 'a'
    maxi2 = 0
    for i in a:
        if k - (ord(i) - 97) >= 0:
            maxi = max(maxi, i)
            m[maxi] = 'a'
        else:
            maxi2 = i
            k -= ord(maxi) - 97
            m[maxi2] = chr(ord(i) - k)
            break
    res = ''
    for i in a:
        if i <= maxi:
            res += 'a'
        elif maxi2 == 0:
            res += i
        elif maxi2 >= i > m[maxi2]:
            res += m[maxi2]
        else:
            res += i
    return res
t = int(input())
for _ in range(t):
    (n, k) = map(int, input().split())
    a = input()
    res2 = solve(n, k, a)
    print(res2)

Solution (Python):
def solve(s: str, k: int):
    if k >= 25:
        return 'a' * len(s)
    bottom = ord('a')
    for character in s:
        if k == 0:
            break
        character_order = ord(character)
        distance = character_order - bottom
        if distance <= 0:
            continue
        if distance <= k:
            k -= distance
            bottom = character_order
        else:
            while k > 0:
                next_character_order = character_order - 1
                next_character = chr(next_character_order)
                s = s.replace(character, next_character)
                character_order = next_character_order
                character = next_character
                k -= 1
    for character_order in range(bottom, ord('a'), -1):
        character = chr(character_order)
        s = s.replace(character, 'a')
    return s
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        (n, k) = map(int, input().split())
        s = input()
        print(solve(s, k))

Solution (Python):
from sys import stdin
stinput = lambda : stdin.readline()[:-1]
ii = lambda : int(stinput())
t = ii()
for _ in range(t):
    (n, k) = map(int, stinput().split())
    s = stinput()
    if k >= 25:
        print('a' * n)
    else:
        k1 = k
        ind = 0
        m = 'a'
        ans = 'z' * n
        while ind < len(s) and ord(s[ind]) - ord('a') <= k1:
            if s[ind] > m:
                m = s[ind]
            ind += 1
        if ind < len(s):
            r = k1 - (ord(m) - ord('a'))
            sec = s[ind]
            sec_new = chr(ord(sec) - r)
            ans = ''
            for x in s:
                if ind != 0 and x <= m:
                    ans += 'a'
                elif m < x <= sec:
                    if x > sec_new:
                        ans += sec_new
                    else:
                        ans += x
                else:
                    ans += x
            print(ans)
        else:
            print('a' * n)