K-beautiful Strings (Codeforces 1493C)
Tags: Greedy, strings

You are given a string $$$s$$$ consisting of lowercase English letters and a number $$$k$$$. Let's call a string consisting of lowercase English letters beautiful if the number of occurrences of each letter in that string is divisible by $$$k$$$. You are asked to find the lexicographically smallest beautiful string of length $$$n$$$, which is lexicographically greater or equal to string $$$s$$$. If such a string does not exist, output $$$-1$$$.A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:   $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;  in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$. 

Input: The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10\,000$$$) — the number of test cases.The next $$$2 \cdot T$$$ lines contain the description of test cases. The description of each test case consists of two lines.The first line of the description contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^5$$$) — the length of string $$$s$$$ and number $$$k$$$ respectively.The second line contains string $$$s$$$ consisting of lowercase English letters.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case output in a separate line lexicographically smallest beautiful string of length $$$n$$$, which is greater or equal to string $$$s$$$, or $$$-1$$$ if such a string does not exist.

Note: In the first test case "acac" is greater than or equal to $$$s$$$, and each letter appears $$$2$$$ or $$$0$$$ times in it, so it is beautiful.In the second test case each letter appears $$$0$$$ or $$$1$$$ times in $$$s$$$, so $$$s$$$ itself is the answer.We can show that there is no suitable string in the third test case.In the fourth test case each letter appears $$$0$$$, $$$3$$$, or $$$6$$$ times in "abaabaaab". All these integers are divisible by $$$3$$$.

Sample Inputs:
4
4 2
abcd
3 1
abc
4 3
aaaa
9 3
abaabaaaa

Sample Outputs:
acac
abc
-1
abaabaaab

Solution (Python):
import threading
import sys
threading.stack_size(16 * 2048 * 2048)
sys.setrecursionlimit(100010)

def getnext(index, fre, k, s, flag):
    if sum(fre) > len(s) - index:
        return 'ERROR'
    if index == len(s):
        return ''
    cur = ord(s[index]) - 97
    if not flag:
        nexts = ''
        spare = len(s) - index - sum(fre)
        if spare % k == 0:
            nexts += 'a' * (spare // k * k)
        for j in range(26):
            if fre[j] > 0:
                nexts += chr(j + 97) * fre[j]
        return nexts
    nexts = 'ERROR'
    for j in range(cur, 26):
        if j > cur and flag:
            flag = False
        fre[j] -= 1
        if fre[j] < 0:
            fre[j] += k
        temp = getnext(index + 1, fre, k, s, flag)
        if temp != 'ERROR':
            nexts = chr(j + 97) + temp
            return nexts
        fre[j] += 1
        if fre[j] == k:
            fre[j] = 0
    return nexts

def main():
    T = int(input())
    t = 1
    while t <= T:
        (n, k) = list(map(int, input().split()))
        s = input()
        if n % k > 0:
            print(-1)
            t += 1
            continue
        fre = [0] * 26
        ans = getnext(0, fre, k, s, True)
        print(ans)
        t += 1
threading.Thread(target=main).start()

Solution (Python):
import heapq
from math import sqrt
import operator
import sys
inf_var = 0
if inf_var == 1:
    inf = open('input.txt', 'r')
else:
    inf = sys.stdin
input = inf.readline

def read_one_int():
    return int(input().rstrip('\n'))

def read_list_of_ints():
    res = [int(val) for val in input().rstrip('\n').split(' ')]
    return res

def read_str():
    return input().rstrip()

def check_substr(string, pos, need_ch_map, k):
    res_str = ''
    budget = len(string)
    for i in range(0, pos + 1):
        if need_ch_map[string[i]] == 0:
            if budget == 0:
                return ''
            need_ch_map[string[i]] += k - 1
            budget -= k
        else:
            need_ch_map[string[i]] -= 1
        res_str += string[i]
    i = pos + 1
    while i < len(string):
        if string[i] == 'z':
            if need_ch_map['z']:
                need_ch_map['z'] -= 1
                res_str += 'z'
                i += 1
                continue
            elif budget == 0:
                return ''
            else:
                need_ch_map['z'] += k - 1
                budget -= k
                res_str += 'z'
                i += 1
                continue
        alph = 'abcdefghijklmnopqrstuvwxyz'
        cur_ch_pos = alph.find(string[i])
        found = False
        for ch_num in range(cur_ch_pos + 1, len(alph)):
            next_ch = alph[ch_num]
            if need_ch_map[next_ch]:
                need_ch_map[next_ch] -= 1
                res_str += next_ch
                i += 1
                found = True
                break
            elif budget > 0:
                need_ch_map[next_ch] += k - 1
                budget -= k
                res_str += next_ch
                i += 1
                found = True
                break
        if found:
            break
        if need_ch_map[string[i]]:
            need_ch_map[string[i]] -= 1
            res_str += string[i]
            i += 1
            continue
        elif budget == 0:
            return ''
        else:
            need_ch_map[string[i]] += k - 1
            budget -= k
            res_str += string[i]
            i += 1
            continue
    need_ch_map['a'] += budget
    for (ch, cnt) in need_ch_map.items():
        res_str += ch * cnt
    return res_str

def find_next_ch(ch):
    alph = 'abcdefghijklmnopqrstuvwxyz'
    return alph[alph.find(ch) + 1]

def check_seq(n, k, string):
    if n % k:
        return -1
    alph = 'abcdefghijklmnopqrstuvwxyz'
    l = -1
    r = n - 1
    empty_ch_map = {}
    for ch in alph:
        empty_ch_map[ch] = 0
    res_str = ''
    while l <= r:
        mid = l + r >> 1
        cur_res_str = check_substr(string, mid, empty_ch_map.copy(), k)
        if cur_res_str:
            res_str = cur_res_str
        if cur_res_str:
            l = mid + 1
        else:
            r = mid - 1
    return res_str

def main():
    cnt = read_one_int()
    for _ in range(cnt):
        (n, k) = read_list_of_ints()
        string = read_str()
        res = check_seq(n, k, string)
        if not res:
            print('-1')
        else:
            print(res)
if __name__ == '__main__':
    main()

Solution (Python):
def solve():
    for i in range(int(input())):
        (n, k) = map(int, input().split())
        s = input().strip()
        if k == 1:
            print(s)
            continue
        if n % k != 0:
            print(-1)
            continue
        want = [0] * 26
        need = 0
        i = 0
        best = -1
        A = ord('a')
        for c in s:
            v = ord(c) - A
            if v < 25:
                for j in range(v + 1, 26):
                    if want[j] == 0:
                        if need + k - 1 <= n - i - 1:
                            best = i
                            break
                    elif need - 1 <= n - i - 1:
                        best = i
                        break
            if want[v] == 0:
                want[v] = k - 1
                need += k - 1
            else:
                need -= 1
                want[v] -= 1
            i += 1
        if need == 0:
            print(s)
            continue
        if best == -1:
            print(-1)
            continue
        want = [0] * 26
        need = 0
        i = 0
        for c in s:
            v = ord(c) - A
            if i == best:
                res = list(s[:i])
                for j in range(v + 1, 26):
                    if want[j] == 0:
                        if need + k - 1 <= n - i - 1:
                            need += k - 1
                            want[j] = k - 1
                            res.append(chr(j + A))
                            break
                    elif need - 1 <= n - i - 1:
                        res.append(chr(j + A))
                        want[j] -= 1
                        need -= 1
                        break
                while need < n - i - 1:
                    want[0] += k
                    need += k
                for z in range(26):
                    for _ in range(want[z]):
                        res.append(chr(z + A))
                print(''.join(res))
                break
            if want[v] == 0:
                want[v] = k - 1
                need += k - 1
            else:
                need -= 1
                want[v] -= 1
            i += 1
solve()