Maximize the Remaining String (Codeforces 1506G)
Tags: Greedy, strings

You are given a string $$$s$$$, consisting of lowercase Latin letters. While there is at least one character in the string $$$s$$$ that is repeated at least twice, you perform the following operation:   you choose the index $$$i$$$ ($$$1 \le i \le |s|$$$) such that the character at position $$$i$$$ occurs at least two times in the string $$$s$$$, and delete the character at position $$$i$$$, that is, replace $$$s$$$ with $$$s_1 s_2 \ldots s_{i-1} s_{i+1} s_{i+2} \ldots s_n$$$. For example, if $$$s=$$$"codeforces", then you can apply the following sequence of operations:   $$$i=6 \Rightarrow s=$$$"codefrces";  $$$i=1 \Rightarrow s=$$$"odefrces";  $$$i=7 \Rightarrow s=$$$"odefrcs"; Given a given string $$$s$$$, find the lexicographically maximum string that can be obtained after applying a certain sequence of operations after which all characters in the string become unique.A string $$$a$$$ of length $$$n$$$ is lexicographically less than a string $$$b$$$ of length $$$m$$$, if:   there is an index $$$i$$$ ($$$1 \le i \le \min(n, m)$$$) such that the first $$$i-1$$$ characters of the strings $$$a$$$ and $$$b$$$ are the same, and the $$$i$$$-th character of the string $$$a$$$ is less than $$$i$$$-th character of string $$$b$$$;  or the first $$$\min(n, m)$$$ characters in the strings $$$a$$$ and $$$b$$$ are the same and $$$n < m$$$. For example, the string $$$a=$$$"aezakmi" is lexicographically less than the string $$$b=$$$"aezus".

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$). Then $$$t$$$ test cases follow.Each test case is characterized by a string $$$s$$$, consisting of lowercase Latin letters ($$$1 \le |s| \le 2 \cdot 10^5$$$).It is guaranteed that the sum of the lengths of the strings in all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output the lexicographically maximum string that can be obtained after applying a certain sequence of operations after which all characters in the string become unique.


Sample Inputs:
6
codeforces
aezakmi
abacaba
convexhull
swflldjgpaxs
myneeocktxpqjpz

Sample Outputs:
odfrces
ezakmi
cba
convexhul
wfldjgpaxs
myneocktxqjpz

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
MOD = 10 ** 9 + 7

def solve():
    S = input().rstrip()
    d = {i: v for (v, i) in enumerate(S)}
    res = []
    seen = set()
    for (i, s) in enumerate(S):
        if s not in seen:
            while res and s > res[-1] and (d[res[-1]] > i):
                seen.discard(res.pop())
            res.append(s)
            seen.add(s)
    print(''.join(res))
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        solve()

Solution (Python):
from collections import Counter
t = int(input())

def removeDuplicateLetters(s):
    stk = []
    count = Counter(s)
    st = set()
    for i in range(len(s)):
        while stk and count[stk[-1]] >= 1 and (s[i] > stk[-1]) and (s[i] not in st):
            st.remove(stk[-1])
            stk.pop()
        count[s[i]] -= 1
        if s[i] not in st:
            stk.append(s[i])
            st.add(s[i])
    return ''.join(stk)
for _ in range(t):
    s = input()
    print(removeDuplicateLetters(s))

Solution (Python):
import re
import sys
exit = sys.exit
from bisect import bisect_left as bsl, bisect_right as bsr
from collections import Counter, defaultdict as ddict, deque
from functools import lru_cache
cache = lru_cache(None)
from heapq import *
from itertools import *
from math import inf
from pprint import pprint as pp
enum = enumerate
ri = lambda : int(rln())
ris = lambda : list(map(int, rfs()))
rln = sys.stdin.readline
rl = lambda : rln().rstrip('\n')
rfs = lambda : rln().split()
mod = 1000000007
d4 = [(0, -1), (1, 0), (0, 1), (-1, 0)]
d8 = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]
t = ri()
for _ in range(t):
    s = rl()
    n = len(s)
    last = {c: i for (i, c) in enum(s)}
    last[''] = -1
    used = {''}
    ans = ['']
    for (i, c) in enum(s):
        if c in used:
            continue
        while ans[-1] < c and i < last[ans[-1]]:
            used.discard(ans.pop())
        ans.append(c)
        used.add(c)
    print(''.join(ans))