Minimum Notation (Codeforces 1730C)
Tags: Greedy, sortings

You have a string $$$s$$$ consisting of digits from $$$0$$$ to $$$9$$$ inclusive. You can perform the following operation any (possibly zero) number of times:   You can choose a position $$$i$$$ and delete a digit $$$d$$$ on the $$$i$$$-th position. Then insert the digit $$$\min{(d + 1, 9)}$$$ on any position (at the beginning, at the end or in between any two adjacent digits). What is the lexicographically smallest string you can get by performing these operations?A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ of the same length if and only if the following holds:   in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a smaller digit than the corresponding digit in $$$b$$$. 

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then the test cases follow.Each test case consists of a single line that contains one string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$) — the string consisting of digits. Please note that $$$s$$$ is just a string consisting of digits, so leading zeros are allowed.It is guaranteed that the sum of lengths of $$$s$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: Print a single string — the minimum string that is possible to obtain.

Note: In the first test case:   Delete $$$8$$$ and insert $$$9$$$ at the end of the notation. The resulting notation is $$$04299$$$.  Delete $$$4$$$ and insert $$$5$$$ in the $$$3$$$-rd position of the notation. The resulting notation is $$$02599$$$. Nothing needs to be done in the second and third test cases.

Sample Inputs:
4
04829
9
01
314752277691991

Sample Outputs:
02599
9
01
111334567888999

Solution (Python):
import sys
import copy
import heapq
import bisect
import functools
from math import *
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import groupby
from itertools import accumulate
from decimal import Decimal, ROUND_HALF_UP
readline = lambda : sys.stdin.readline().rstrip()

def solve():
    s = list(map(int, readline()))
    n = len(s)
    x = 9
    cnt = [0 for _ in range(10)]
    for i in range(n - 1, -1, -1):
        d = s[i]
        if s[i] <= x:
            cnt[d] += 1
            x = s[i]
        else:
            cnt[min(d + 1, 9)] += 1
    print(''.join([str(i) * cnt[i] for i in range(10) if cnt[i] != 0]))

def main():
    t = 1
    t = int(readline())
    for i in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import sys, os, io
from collections import *
from bisect import *
from math import *
from heapq import heapify, heappop, heappush
from bisect import bisect_left, bisect_right
from string import ascii_lowercase
MOD = int(1000000000.0) + 7
inf = float('inf')

def fileInput():
    sys.stdin = open('input.txt', 'r')

def lst():
    return list(map(int, input().strip().split()))

def integer():
    return int(input())

def string():
    return input()

def matrixNum(m, n):
    return [lst() for i in range(m)]
yn = ['Yes', 'No']
yn = [i.upper() for i in yn]

def solve():
    s = list(string())
    mini = '9'
    for i in range(len(s) - 1, -1, -1):
        if s[i] <= mini:
            mini = s[i]
        else:
            s[i] = str(min(9, 1 + int(s[i])))
    s.sort()
    print(''.join(s))
t = 1
t = integer()
for _ in range(t):
    solve()

Solution (Python):
import sys
from collections import defaultdict, Counter
sys.setrecursionlimit(1000000)
input = lambda : sys.stdin.readline().strip()

def solve():
    s = input()
    n = len(s)
    lst = []
    (ans1, ans2) = ([], [])
    dic = defaultdict(list)
    for (i, x) in enumerate(s):
        lst.append(int(x))
        dic[int(x)].append(i)
    lst = list(set(lst))
    lst.sort()
    idx = 0
    cnt = Counter()
    for x in lst:
        ans1 += [x] * (len(dic[x]) - cnt[x])
        for y in dic[x]:
            while idx < y:
                ans2.append(min(int(s[idx]) + 1, 9))
                cnt[int(s[idx])] += 1
                idx += 1
            if idx == y:
                idx += 1
            if idx == n:
                idx -= 1
    ans = sorted(ans1 + ans2)
    res = ''
    for x in ans:
        res += str(x)
    print(res)

def solve1():
    s = input()
    (st, tmp) = ([], [])
    for x in s:
        x = int(x)
        while len(st) > 0 and x < st[-1]:
            tmp.append(min(st[-1] + 1, 9))
            st.pop()
        st.append(x)
    ans = sorted(st + tmp)
    res = ''
    for x in ans:
        res += str(x)
    print(res)
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        solve1()