Nearest Beautiful Number (hard version) (Codeforces 1560F2)
Tags: Greedy, bitmasks

It is a complicated version of problem F1. The difference between them is the constraints (F1: $$$k \le 2$$$, F2: $$$k \le 10$$$).You are given an integer $$$n$$$. Find the minimum integer $$$x$$$ such that $$$x \ge n$$$ and the number $$$x$$$ is $$$k$$$-beautiful.A number is called $$$k$$$-beautiful if its decimal representation having no leading zeroes contains no more than $$$k$$$ different digits. E.g. if $$$k = 2$$$, the numbers $$$3434443$$$, $$$55550$$$, $$$777$$$ and $$$21$$$ are $$$k$$$-beautiful whereas the numbers $$$120$$$, $$$445435$$$ and $$$998244353$$$ are not.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.Each test case consists of one line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le k \le 10$$$).

Output: For each test case output on a separate line $$$x$$$ — the minimum $$$k$$$-beautiful integer such that $$$x \ge n$$$.


Sample Inputs:
6
2021 3
177890 2
34512 3
724533 4
998244353 1
12345678 10

Sample Outputs:
2021
181111
34533
724542
999999999
12345678

Solution (Python):
def get_input():
    al = []
    for c in range(int(input())):
        t = input().split(' ')
        el = [t[0], int(t[1])]
        al.append(el)
    return al

def find_best(n, j, s):
    b = ':'
    m = ':'
    for k in s:
        if k < m:
            m = k
        if n[j] < k and k < b:
            b = k
    if b == ':':
        return False
    else:
        return n[:j] + b + m * (len(n) - j - 1)

def solve(n, k):
    if k == 1:
        for i in range(1, len(n)):
            if n[i] > n[0]:
                return str(int(n[0]) + 1) * len(n)
            elif n[i] < n[0]:
                break
        return n[0] * len(n)
    s = []
    for i in range(len(n)):
        if n[i] not in s:
            if len(s) == k:
                rf = find_best(n, i, s)
                if rf != False:
                    return rf
                for j in range(i - 1, -1, -1):
                    if n[j] == '9':
                        continue
                    elif n[j] in n[:j]:
                        rf = find_best(n, j, s)
                        if rf != False:
                            return rf
                    else:
                        c = str(int(n[j]) + 1)
                        cm = c
                        for l in range(j):
                            if n[l] < cm:
                                cm = n[l]
                        d = []
                        for l in range(j):
                            if n[l] not in d:
                                d.append(n[l])
                        if c not in d:
                            d.append(c)
                        if len(d) < k:
                            return n[:j] + c + '0' * (len(n) - j - 1)
                        return n[:j] + c + min(cm, c) * (len(n) - j - 1)
            s.append(n[i])
    return n

def main():
    arr_list = get_input()
    for n in arr_list:
        r = solve(n[0], n[1])
        print(r)
main()

Solution (Python):
def get_input():
    al = []
    for c in range(int(input())):
        t = input().split(' ')
        el = [t[0], int(t[1])]
        al.append(el)
    return al

def find_best(n, j, s):
    b = ':'
    m = ':'
    for k in s:
        if k < m:
            m = k
        if n[j] < k and k < b:
            b = k
    if b == ':':
        return False
    else:
        return n[:j] + b + m * (len(n) - j - 1)

def solve(n, k):
    s = []
    for i in range(len(n)):
        if n[i] not in s:
            if len(s) == k:
                rf = find_best(n, i, s)
                if rf != False:
                    return rf
                for j in range(i - 1, -1, -1):
                    if n[j] == '9':
                        continue
                    elif n[j] in n[:j]:
                        rf = find_best(n, j, s)
                        if rf != False:
                            return rf
                    else:
                        c = str(int(n[j]) + 1)
                        cm = c
                        for l in range(j):
                            if n[l] < cm:
                                cm = n[l]
                        d = []
                        for l in range(j):
                            if n[l] not in d:
                                d.append(n[l])
                        if c not in d:
                            d.append(c)
                        if len(d) < k:
                            return n[:j] + c + '0' * (len(n) - j - 1)
                        return n[:j] + c + min(cm, c) * (len(n) - j - 1)
            s.append(n[i])
    return n

def main():
    arr_list = get_input()
    for n in arr_list:
        r = solve(n[0], n[1])
        print(r)
main()

Solution (Python):
def get_input():
    al = []
    for c in range(int(input())):
        t = input().split(' ')
        el = [t[0], int(t[1])]
        al.append(el)
    return al

def find_best(n, j, s):
    b = ':'
    m = ':'
    for k in s:
        if k < m:
            m = k
        if n[j] < k and k < b:
            b = k
    if b == ':':
        return False
    else:
        return n[:j] + b + m * (len(n) - j - 1)

def solve(n, k):
    if k == 1:
        for i in range(1, len(n)):
            if n[i] > n[0]:
                return str(int(n[0]) + 1) * len(n)
            elif n[i] < n[0]:
                break
        return n[0] * len(n)
    s = []
    for i in range(len(n)):
        if n[i] not in s:
            if len(s) == k:
                rf = find_best(n, i, s)
                if rf != False:
                    return rf
                for j in range(i - 1, -1, -1):
                    if n[j] == '9':
                        continue
                    elif n[j] in n[:j]:
                        rf = find_best(n, j, s)
                        if rf != False:
                            return rf
                    else:
                        c = str(int(n[j]) + 1)
                        cm = c
                        for l in range(j):
                            if n[l] < cm:
                                cm = n[l]
                        d = []
                        for l in range(j):
                            if n[l] not in d:
                                d.append(n[l])
                        if c not in d:
                            d.append(c)
                        if len(d) < k:
                            return n[:j] + c + '0' * (len(n) - j - 1)
                        return n[:j] + c + min(cm, c) * (len(n) - j - 1)
            s.append(n[i])
    return n

def main():
    arr_list = get_input()
    for n in arr_list:
        r = solve(n[0], n[1])
        print(r)
main()