Problem:
 Score : 600 points    Problem Statement A subsequence of a string S is a string that can be obtained by deleting zero or more characters from S without changing the order of the remaining characters.
For example, arc , artistic and (an empty string) are all subsequences of artistic ; abc and ci are not.  You are given a string A consisting of lowercase English letters.
Find the shortest string among the strings consisting of lowercase English letters that are not subsequences of A .
If there are more than one such string, find the lexicographically smallest one among them.      Constraints  1 \leq |A| \leq 2 \times 10^5  A consists of lowercase English letters.         Input Input is given from Standard Input in the following format:  A       Output Print the lexicographically smallest string among the shortest strings consisting of lowercase English letters that are not subsequences of A .        Sample Input 1 atcoderregularcontest      Sample Output 1 b  The string atcoderregularcontest contains a as a subsequence, but not b .       Sample Input 2 abcdefghijklmnopqrstuvwxyz      Sample Output 2 aa       Sample Input 3 frqnvhydscshfcgdemurlfrutcpzhopfotpifgepnqjxupnskapziurswqazdwnwbgdhyktfyhqqxpoidfhjdakoxraiedxskywuepzfniuyskxiyjpjlxuqnfgmnjcvtlpnclfkpervxmdbvrbrdn      Sample Output 3 aca

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


a = input()
n = len(a)
s = set()
l = []
i = n-1
prv = n
for c in a[::-1]:
    s.add(c)
    if len(s)==26:
        s = set()
        l.append((i,prv))
        prv = i
    i -= 1
def sub(i,j):
    """[i,j)に含まれない文字のうちの最小
    """

    al = set([chr(v) for v in range(ord("a"), ord("z")+1)])
    for ind in range(i,j):
        al.discard(a[ind])
    return min(al)
ans = []
c = sub(0,prv)
ans.append(c)
while l:
    i,j = l.pop()
    for ind in range(i,n):
        if a[ind]==c:
            break
    c = sub(ind+1,j)
    ans.append(c)
ans = "".join(ans)


print(ans)

Solution (Python):
from bisect import bisect_right, bisect_left
A = [ord(t) - ord("a") for t in input()]
n = len(A)
alf = [[] for i in range(26)]
for i, a in enumerate(A):
    alf[a].append(i)
for i in range(26):
    alf[i].append(n+1)

first = [n]
appeard = [0] * 26
cnt = 0
for i in range(n - 1, -1, -1):
    a = A[i]
    if 1 - appeard[a]:
        appeard[a] = 1
        cnt += 1
    if cnt == 26:
        first.append(i)
        cnt = 0
        appeard = [0] * 26

def ntoa(x):
    return chr(ord("a") + x)

first.reverse()
ans = ""

for i in range(26):
    if 1 - appeard[i]:
        ans += ntoa(i)
        if alf[i]:
            last = alf[i][0]
        break
if len(first) == 1:
    print(ans)
    exit()

for j in range(len(first) - 1):
    for i in range(26):
        nxt = alf[i][bisect_right(alf[i], last)]
        if nxt >= first[j+1]:
            ans += ntoa(i)
            last = nxt
            break
print(ans)

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline


s = input()

def next_index(N,s):
    D = [-1]*26
    E = [None]*(N+1)
    cA = ord('a')
    for i in range(N-1, -1, -1):
        E[i+1] = D[:]
        D[ord(s[i])-cA] = i
    E[0] = D
    return E

n = len(s)
nxt = next_index(n,s)

"""
for i in nxt:
    print(i[:4])
"""


dp = [0]*(n+1)
for i in range(n-1,-1,-1):
    idx = max(nxt[i])
    bad = min(nxt[i])
    dp[i] = dp[idx+1]+1 if bad != -1 else 0




k = dp[0]+1
ans = [None]*k

v = 0
for i in range(k):
    
    if v==n:
        ans[-1] = 0
        break

    for j in range(26):
        
        if nxt[v][j]==-1 or dp[nxt[v][j] + 1] < dp[v]:
            ans[i] = j
            v = nxt[v][j]+1
            break


def f(x):
    return chr(x+ord("a"))

a = "".join(map(f,ans))
print(a)



"""
x = [chr(ord("z")-i) for i in range(26)]
x = "".join(x)
print(x)
"""

Solution (Python):
import sys
input = sys.stdin.readline

A = input().rstrip()
dp = [chr(c) for c in range(ord('a'), ord('z')+1)]
for c in A[::-1]:
    s = min(dp, key=lambda x: len(x))
    dp[ord(c) - ord('a')] = c + s
print(min(dp, key=lambda x: len(x)))

Solution (Python):
from collections import deque


A = input()
N = len(A)
a = ord('a')

edge = [[N + 1] * 26 for _ in range(N + 1)]
for i in range(N - 1, -1, -1):
    for j in range(26):
        edge[i][j] = edge[i + 1][j]
    c = ord(A[i]) - a
    edge[i][c] = i + 1  


recon = [None] * (N + 2)  
q = deque()
q.append(0)  
while q:
    i = q.popleft()
    if i == N + 1:  
        break
    for j in range(26):
        ni = edge[i][j]
        if recon[ni] is None:  
            recon[ni] = (i, chr(a + j))
            q.append(ni)

i = N + 1
ans = []
while i > 0:
    pi, c = recon[i]
    ans.append(c)
    i = pi

print(''.join(reversed(ans)))

Solution (Python):
def calcNext(s):
    n = len(s)
    res = [[n+1] * 26 for _ in range(n+1)]
    for i in range(n-1, -1, -1):
        for j in range(26):
            res[i][j] = res[i+1][j]
        res[i][ord(s[i]) - ord('a')] = i
    return res

def solve(s):
    n = len(s)
    nx = calcNext(s)
    dp = [n + 1] * (n + 1)
    recon = ['a'] * (n + 1)
    dp[n] = 1
    for i in range(n-1, -1, -1):
        for j in range(26):
            if nx[i][j] == n + 1:
                if dp[i] > 1:
                    dp[i] = 1
                    recon[i] = chr(ord('a') + j)
            else:
                if dp[nx[i][j] + 1] + 1 < dp[i]:
                    dp[i] = dp[nx[i][j] + 1] + 1
                    recon[i] = chr(ord('a') + j)
    res = ''
    idx = 0
    while idx <= n:
        res += recon[idx]
        idx = nx[idx][ord(recon[idx]) - ord('a')] + 1
    return res

S = input()
print(solve(S))

Solution (Python):
def main():
    
    
    
    
    A = input()
    N = len(A)
    a = ord('a')

    INF = N
    na = [[INF] * 26 for _ in range(N + 1)]
    for i in range(N - 1, -1, -1):
        c = ord(A[i]) - a
        for j in range(26):
            na[i][j] = na[i + 1][j]
        na[i][c] = i

    dp = [INF] * (N + 1)
    dp[N] = 1
    recon = [None] * (N + 1)
    for i in range(N - 1, -1, -1):
        for j in range(26):
            ni = na[i][j]
            if ni == N:
                if dp[i] > 1:
                    dp[i] = 1
                    recon[i] = (chr(a + j), N)
            elif dp[i] > dp[ni + 1] + 1:
                dp[i] = dp[ni + 1] + 1
                recon[i] = (chr(a + j), ni + 1)

    
    
    
    

    i = 0
    ans = []
    while i < N:
        c, ni = recon[i]
        ans.append(c)
        i = ni

    print(''.join(ans))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *
from bisect import *

A = input()[:-1]
K = [0]*(len(A)) 
s = set()
cnt = 1

for i in range(len(A)-1, -1, -1):
    K[i] = cnt
    s.add(A[i])
    
    if len(s)==26:
        cnt += 1
        s = set()

d = defaultdict(list)

for i in range(len(A)):
    d[A[i]].append(i)

ans = []
now = -1

for i in range(cnt):
    for alpha in 'abcdefghijklmnopqrstuvwxyz':
        idx = bisect_right(d[alpha], now)
        
        if idx==len(d[alpha]):
            ans.append(alpha)
            break
        
        nex = d[alpha][idx]
        
        if K[nex]==cnt-i-1:
            now = nex
            ans.append(alpha)
            break

print(''.join(ans))

Solution (Python):

from sys import stdout







def main():
    ans = solve_case()
    stdout.write("{}\n".format(ans))

def solve_case():
    S = read_str()

    len_s = len(S)
    int_s = [ord(c) - ord('a') for c in S]

    
    next_char_pos = make_list((len_s + 1, 26), len_s)
    for from_idx in reversed(range(len_s)):
        for letter_idx in range(26):
            if int_s[from_idx] == letter_idx:
                pos = from_idx
            else:
                pos = next_char_pos[from_idx+1][letter_idx]
            next_char_pos[from_idx][letter_idx] = pos

    
    non_subseq_len = make_list([len_s + 2], len_s + 1)
    non_subseq_len[len_s] = 1
    non_subseq_len[len_s + 1] = 0
    ans_next_pos = make_list([len_s + 1], len_s)
    ans_letter = make_list([len_s + 1], -1)
    for from_idx in reversed(range(len_s)):
        for letter_idx in range(26):
            new_len = non_subseq_len[next_char_pos[from_idx][letter_idx] + 1] + 1
            if non_subseq_len[from_idx] > new_len:
                non_subseq_len[from_idx] = new_len
                ans_letter[from_idx] = letter_idx
                ans_next_pos[from_idx] = next_char_pos[from_idx][letter_idx] + 1

    ans = ''
    idx = 0
    while idx < len(S):
        ans += chr(ord('a') + ans_letter[idx])
        idx = ans_next_pos[idx]
    return ans



def read_str(): return input()
def read_int(): return int(input())
def read_str_list(): return input().split(' ')
def read_int_list(): return list(map(int, input().split(' ')))
def read_lines(n, read_func): return [read_func() for _ in range(n)]
def list_to_str(l, sep=' '): return sep.join(map(str, l))
l2s = list_to_str

def make_list(shape, value=None):
    if len(shape) == 1:
        return [value] * shape[0]
    return [make_list(shape[1:], value) for _ in range(shape[0])]

if __name__ == '__main__':
    
    main()

Solution (Python):

from sys import stdout







def main():
    ans = solve_case()
    stdout.write("{}\n".format(ans))

def solve_case():
    S = read_str()

    len_s = len(S)
    int_s = [ord(c) - ord('a') for c in S]

    
    next_char_pos = make_list((len_s + 1, 26), len_s)
    for from_idx in reversed(range(len_s)):
        for letter_idx in range(26):
            if int_s[from_idx] == letter_idx:
                pos = from_idx
            else:
                pos = next_char_pos[from_idx+1][letter_idx]
            next_char_pos[from_idx][letter_idx] = pos

    
    non_subseq_len = make_list([len_s + 2], len_s + 1)
    non_subseq_len[len_s] = 1
    non_subseq_len[len_s + 1] = 0
    ans_next_pos = make_list([len_s + 1], len_s)
    ans_letter = make_list([len_s + 1], -1)
    for from_idx in reversed(range(len_s)):
        for letter_idx in range(26):
            new_len = non_subseq_len[next_char_pos[from_idx][letter_idx] + 1] + 1
            if non_subseq_len[from_idx] > new_len:
                non_subseq_len[from_idx] = new_len
                ans_letter[from_idx] = letter_idx
                ans_next_pos[from_idx] = next_char_pos[from_idx][letter_idx] + 1

    ans = ''
    idx = 0
    while idx < len(S):
        ans += chr(ord('a') + ans_letter[idx])
        idx = ans_next_pos[idx]
    return ans



def read_str(): return input()
def read_int(): return int(input())
def read_str_list(): return input().split(' ')
def read_int_list(): return list(map(int, input().split(' ')))
def read_lines(n, read_func): return [read_func() for _ in range(n)]
def list_to_str(l, sep=' '): return sep.join(map(str, l))
l2s = list_to_str

def make_list(shape, value=None):
    if len(shape) == 1:
        return [value] * shape[0]
    return [make_list(shape[1:], value) for _ in range(shape[0])]

if __name__ == '__main__':
    
    main()

Solution (Python):
import bisect

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

A=input()
N=len(A)

dic={moji:[] for moji in alphabetlist}
dp=[0 for i in range(N)]
check=set([A[-1]])
dic[A[-1]].append(N-1)
for i in range(N-2,-1,-1):
    check.add(A[i])
    dic[A[i]].append(i)
    if len(check)==26:
        dp[i]=dp[i+1]+1
        check=set([])
    else:
        dp[i]=dp[i+1]

for moji in alphabetlist:
    dic[moji].sort()

L=dp[0]+1
ans=[]
pos=-1
flag=0

for i in range(L-1):
    if flag==1:
        break
    for moji in alphabetlist:
        if dic[moji]:
            index=bisect.bisect_left(dic[moji],pos)
            npos=dic[moji][index]
            if npos+1<N and dp[npos+1]<L-(i+1):
                pos=npos+1
                ans.append(moji)
                break
            elif npos==N-1:
                pos=N
                ans.append(moji)
                flag=1
                break

if pos==N:
    ans.append("a")
    print("".join(ans))
else:
    s=set([])
    for i in range(pos,N):
        s.add(A[i])
    for moji in alphabetlist:
        if moji not in s:
            ans.append(moji)
            break
    print("".join(ans))

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    S = list(map(lambda c : ord(c) - ord('a'), input()))
    n = len(S)
    sigma = 26

    
    next = [[-1] * sigma for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        for c in range(sigma):
            next[i][c] = i if S[i] == c else next[i + 1][c]

    
    dp = [INF] * (n + 1)
    dp[n] = 1
    
    character = [None] * (n + 1)
    character[n] = 0
    for i in range(n - 1, -1, -1):
        for c in range(sigma):
            length = 1 if next[i][c] == -1 else 1 + dp[next[i][c] + 1]
            if dp[i] > length:
                dp[i] = length
                character[i] = c

    
    res = []
    now = 0
    while 1:
        res.append(character[now])
        now = next[now][character[now]] + 1
        if now == 0:
            break
    res = ''.join(map(lambda x : chr(x + ord('a')), res))
    print(res)
resolve()

Solution (Python):
A = [ord(a)-97 for a in input()]
N = len(A)
X = [0] * 26
Y = [0] * (N + 2)
NE = [0] * N
R = [N] * 26
s = 0
t = 1
for i in range(N)[::-1]:
    a = A[i]
    if X[a] == 0:
        X[a] = 1
        s += 1
        if s == 26:
            s = 0
            X = [0] * 26
            t += 1
    Y[i] = t
    NE[i] = R[a]
    R[a] = i

ANS = []
ii = 0
for i, a in enumerate(A):
    if i == ii:
        for j in range(26):
            if Y[R[j]+1] < Y[i]:
                ANS.append(j)
                ii = R[j]+1
                break
    R[a] = NE[i]

print("".join([chr(a+97) for a in ANS]))

Solution (Python):
A = [ord(a)-97 for a in input()]
N = len(A)
X = [0] * 26
Y = [0] * (N + 2)
NE = [0] * N
R = [N] * 26
s = 0
t = 1
for i in range(N)[::-1]:
    a = A[i]
    if X[a] == 0:
        X[a] = 1
        s += 1
        if s == 26:
            s = 0
            X = [0] * 26
            t += 1
    Y[i] = t
    NE[i] = R[a]
    R[a] = i

ANS = []
ii = 0
for i, a in enumerate(A):
    if i == ii:
        for j in range(26):
            if Y[R[j]+1] < Y[i]:
                ANS.append(j)
                ii = R[j]+1
                break
    R[a] = NE[i]

print("".join([chr(a+97) for a in ANS]))

Solution (Python):
import bisect
s = input()
n = len(s)
dp = [[0 for i in range(26)] for j in range(n+1)]
flg = [0]*26
prt = []
for i in range(n-1,-1,-1):
  x = ord(s[i])-97
  for j in range(26):
    if j == x:
      dp[i][j] = n-i
      flg[x] = 1
    else:
      dp[i][j] = dp[i+1][j]
  if flg.count(1) == 26:
    prt.append(i)
    flg = [0]*26
ind = 0
ans = []
if not prt:
  for i in range(26):
    if dp[0][i] == 0:
      print(chr(i+97))
      exit()
prt = prt[::-1]
for i in range(26):
  if dp[prt[0]][i] == dp[0][i]:
    ans.append(i)
    break
else:
  ans.append(0)

pnt = prt[0]
flg = 0
while True:
  c = ans[-1]
  if not flg:
    pnt = n-dp[pnt][c]
  flg = 0
  prtp = bisect.bisect_right(prt,pnt)
  if prtp == len(prt):
    for i in range(26):
      if dp[pnt+1][i] == dp[-1][i]:
        ans.append(i)
        break
    else:
      ans.append(0)
    for od in ans:
      print(chr(od+97),end="")
    break
  npnt = prt[prtp]
  for i in range(26):
    if dp[pnt+1][i] == dp[npnt][i]:
      ans.append(i)
      break
  else:
    ans.append(0)
    flg = 1
  pnt = npnt

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc081/tasks/arc081_c

1文字がありうるのは、出てない文字があるとき
2文字がありうるのは、全ての文字が1度出たのち、もう一度すべての文字が1度現れてない場合
つまり答えの文字数はこの方法で分かる

では辞書順最小のものは？
k文字であることがわかっていたとする。
この時、どの文字も最低k-1回出現している
最後の文字は、k回出現してない文字の内、辞書順最小の物
最後から1番目は、k-1回目の出現の後、最後の文字が出ていない者
最後から2番目は、

abcの3文字しかないとする
abababababcab

→この時、求めるのは、?cで、?はc最後に出現するcよりも前に存在しないk-1文字の辞書順最小

abcabcab
→??c
→最後の出現するc以前=abcab以前で存在しない2文字
→?cc
→abで存在しない1文字
→ccc

acbaccbac
→結局再帰的に解ける
→出現回数が最小の文字のうち、辞書順最小の物を答えの最後の文字から決めていき、その文字が最後の出現したind
より前に関して、同じ問題を解く

あとはどうやって計算量を削減するか
その時点で、どの文字が何度出たか、最後の出現したindexはどこか、を記録して置いて再帰的に解く

→方針は合ってる？けど実装してるのが違うよ！
保存しておくのは、全ての文字が何回出揃ったか、とその後どの文字が出ているか。
&各文字が最後にどこで出たか。

あれー？
aaaaaabbbbbbc

→問題は、必ずしも後ろから最適なのを選んで行けばいいわけではなかったこと
→これはあくまで、後ろから見て辞書順最小でしかない…あれまさか？
→正解しちゃったー？？？
"""

A = list(input())
A.reverse()

alp = "abcdefghijklmnopqrstuvwxyz"
alpdic = {}
for i in range(26):
    alpdic[alp[i]] = i

allcol = [0] * (len(A)+1)
apnum =  [ [0] * 26 for i in range(len(A)+1) ]
lastap = [ [0] * 26 for i in range(len(A)+1) ]

for i in range(len(A)):

    for j in range(26):
        apnum[i+1][j] = apnum[i][j]
        lastap[i+1][j] = lastap[i][j]
        allcol[i+1] = allcol[i]

    apnum[i+1][alpdic[A[i]]] |= 1
    if 0 not in apnum[i+1]:
        apnum[i+1] = [0] * 26
        allcol[i+1] += 1
    lastap[i+1][alpdic[A[i]]] = i+1

anslen = allcol[-1]+1
ans = []
nind = len(A)

for i in range(anslen):

    

    minind = 0
    for j in range(26):
        if apnum[nind][j] == 0:
            minind = j
            break
    ans.append(alp[minind])

    nind = lastap[nind][minind]-1


print ("".join(ans))

Solution (Python):
from bisect import bisect_left
A = [ord(i) - 97 for i in input()]

A = A + list(range(26))
A = A[::-1]

dp = [0] * 26
key = [[] for _ in range(26)]
val = [[] for _ in range(26)]
for i, a in enumerate(A) :
  x = min(dp) + 1
  dp[a] = x
  key[a].append(i)
  val[a].append(x)

ret = ''
x = dp[dp.index(min(dp))] + 1
pos = 10 ** 6
while True :
  for i in range(26) :
    if key[i][0] < pos :
      j = bisect_left(key[i], pos) - 1
      if val[i][j] == x - 1 :
        ret += chr(i + 97)
        pos = key[i][j]
        x -= 1
        break
  else :
    break

print(ret)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

    S = input().rstrip('\n')
    N = len(S)

    rank = [0] * N
    seen = [0] * 26
    cnt = 0
    r = 0
    for i in range(N-1, -1, -1):
        j = ord(S[i]) - 97
        if not seen[j]:
            seen[j] = 1
            cnt += 1
        rank[i] = r
        if cnt == 26:
            r += 1
            seen = [0] * 26
            cnt = 0

    ans = []
    for i in range(26):
        if not seen[i]:
            ans.append(i+97)
            break

    i0 = 0
    while ord(S[i0]) != ans[0]:
        i0 += 1
        if i0 == N:
            print(chr(ans[0]))
            exit()
    r = rank[i0]
    seen2 = [0] * 26
    flg = 1
    for i in range(i0+1, N):
        j = ord(S[i])-97
        if flg:
            if rank[i] == r:
                seen2[j] = 1
            else:
                for k in range(26):
                    if not seen2[k]:
                        ans.append(k+97)
                        break
                flg = 0
                seen2 = [0] * 26
                if j == k:
                    r -= 1
                    flg = 1
        else:
            if j != k:
                continue
            else:
                r -= 1
                flg = 1
    for k in range(26):
        if not seen2[k]:
            ans.append(k + 97)
            break
    print(''.join(map(chr, ans)))



if __name__ == '__main__':
    main()

Solution (Python):
S = input()
N = len(S)
INF = N+1
nex = [[INF]*26 for _ in range(N+1)]
for i,c in enumerate(S[::-1]):
    ic = ord(c) - ord('a')
    for j in range(26):
        nex[N-i-1][j] = N-i-1 if j==ic else nex[N-i][j]

dp = [N] * (N+3)
dp[INF] = dp[INF+1] = 0
for i in range(N,-1,-1):
    tmp = INF
    for j in range(26):
        tmp = min(tmp, dp[nex[i][j]+1]+1)
        if tmp == 1: break
    dp[i] = tmp

ans = []
i = 0
for v in range(dp[0]-1,-1,-1):
    for j in range(26):
        if dp[nex[i][j]+1] != v: continue
        ans.append(chr(j + ord('a')))
        i = nex[i][j]+1
        break

print(''.join(ans))

Solution (Python):
a = list(map(lambda x: ord(x)-ord("a"), list(input())))
n = len(a)
m = 26

b = [0]*n
pos = [[] for i in range(m)]
s = set()
cnt = 0
for i in reversed(range(n)):
    b[i] = cnt
    if a[i] not in s:
        s.add(a[i])
    pos[a[i]].append(i)
    if len(s) == m:
        cnt += 1
        s = set()

for i in range(m):
    pos[i].sort()

k = cnt+1

from bisect import bisect_right

ans = []
cur = -1
for i in range(k):
    for j in range(m):
        pj = bisect_right(pos[j], cur)
        if pj == len(pos[j]):
            ans.append(j)
            break
        to = pos[j][pj]
        if b[to] != k-i-1:
            cur = to
            ans.append(j)
            break

ans = "".join(chr(ord("a")+i) for i in ans)
print(ans)

Solution (Python):
a = list(map(lambda x: ord(x)-ord("a"), list(input())))
n = len(a)
m = 26

b = [1]*(n+1)
prev = [n]*m
G = [[] for i in range(n+1)]
for i in reversed(range(n)):
    ai = a[i]
    tmp = min(b[j] for j in prev)
    for j in prev:
        G[i].append(j)
    b[i] = tmp+1
    prev[ai] = i

cnt = min(b[j] for j in prev)
edge = prev
ans = []
for _ in range(cnt):
    for i, to in enumerate(edge):
        if b[to] == cnt-_:
            ans.append(chr(ord("a")+i))
            edge = G[to]
            break
print("".join(ans))

Solution (Python):
from string import ascii_lowercase
from bisect import bisect


def solve(s):
    pos = [[] for _ in range(26)]
    offset = ord('a')
    for i, c in enumerate(s):
        c = ord(c) - offset
        pos[c].append(i)
    for l in pos:
        l.append(len(s))

    all_char_sequence_start_pos = []
    pos_i = [len(l) - 1 for l in pos]
    while all(pi >= 0 for pi in pos_i):
        i = min(l[pi] for pi, l in zip(pos_i, pos))
        all_char_sequence_start_pos.append(i)
        for j in range(26):
            while pos_i[j] >= 0 and pos[j][pos_i[j]] >= i:
                pos_i[j] -= 1
    all_char_sequence_start_pos.reverse()
    ans = []
    curr = -1
    for i in all_char_sequence_start_pos:
        for c in range(26):
            cj = bisect(pos[c], curr)
            j = pos[c][cj]
            if j >= i:
                ans.append(c)
                curr = j
                break
    return ''.join(chr(c + offset) for c in ans)


print(solve(input().strip()))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

a = input() + "$"
n = len(a)

alph = "abcdefghijklmnopqrstuvwxyz"
dp = [-1] * (n + 1)

next_ = [[-1] * (n + 1) for i in range(26)]
for char in range(26):
    tmp = - 1
    for i in range(n)[::-1]:
        if a[i] == alph[char]:
            tmp = i + 1
        next_[char][i] = tmp


def solve():
    for i in range(n + 1)[::-1]:
        tmp = n + 1
        for char in range(26):
            if next_[char][i] == -1:
                dp[i] = 1
                break
            tmp = min(dp[next_[char][i]] + 1 , tmp)
        else:
            dp[i] = tmp

solve()
ans = []
i = 0
while True:
    for char in range(26):
        if next_[char][i] == -1:
            ans.append(alph[char])
            print("".join(ans))
            exit()
        if dp[i] == dp[next_[char][i]] + 1:
            ans.append(alph[char])
            i = next_[char][i]
            break

Solution (Python):
alp = [chr(i) for i in range(97, 97+26)]

import sys
input = sys.stdin.readline

S = input().rstrip()
N = len(S)

dp = [[N]*26 for _ in range(N+1)]

Best = [-1]*(N+1)

for i in reversed(range(N)):
    s = S[i]
    b = 10**14
    for k in range(26):
        if Best[dp[i+1][k]] < b:
            b = Best[dp[i+1][k]]
        if s == alp[k]:
            dp[i][k] = i
        else:
            dp[i][k] = dp[i+1][k]
    Best[i] = b+1

b = 10**14
for k in range(26):
    if Best[dp[0][k]] < b:
        b = Best[dp[0][k]]
L = b+1

ans = ""
ind = -1
for _ in range(L+1):
    best = Best[max(dp[ind+1])]
    for k in range(26):
        if Best[dp[ind+1][k]] == best:
            ans += alp[k]
            if ind != N:
                ind = dp[ind+1][k]
            break
print(ans)

Solution (Python):
from collections import defaultdict
inf = 10**10
A = list(map(lambda x:ord(x)-ord('a'), list(input())))
N = len(A)
abc = 'abcdefghijklmbopqrstuvwxyz'
s_to_i = [[N]*26 for _ in range(N+1)]
for i in range(N)[::-1]:
    for x in range(26):
        s_to_i[i][x] = s_to_i[i+1][x]
    s_to_i[i][A[i]] = i
dp = [0]*(N+2)
dp[-2] = 1
for i in range(N)[::-1]:
    now = max(s_to_i[i])+1
    dp[i] = dp[now]+1
n = dp[0]
now = 0
ans = []
for i in range(n):
    for x in range(26):
        tmp = s_to_i[now][x]+1
        if dp[tmp] <= n-i-1:
            ans.append(chr(x+ord('a')))
            now = tmp
            break
print(*ans, sep = '')

Solution (Python):
from collections import defaultdict
inf = 10**10
A = list(map(lambda x:ord(x)-ord('a'), list(input())))
N = len(A)
abc = 'abcdefghijklmbopqrstuvwxyz'
s_to_i = [[N]*26 for _ in range(N+1)]
for i in range(N)[::-1]:
    for x in range(26):
        s_to_i[i][x] = s_to_i[i+1][x]
    s_to_i[i][A[i]] = i
dp = [0]*(N+2)
dp[-2] = 1
for i in range(N)[::-1]:
    now = max(s_to_i[i])+1
    dp[i] = dp[now]+1
n = dp[0]
now = 0
ans = []
for i in range(n):
    for x in range(26):
        tmp = s_to_i[now][x]+1
        if dp[tmp] <= n-i-1:
            ans.append(chr(x+ord('a')))
            now = tmp
            break
print(*ans, sep = '')

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    inf = 10 ** 7
    s = input()
    n = len(s)
    s += "".join(chr(i + 97) for i in range(26))
    
    
    size = [0] * 26
    pos = [n + i for i in range(26)]
    
    nxt = [-1] * n
    
    for i in range(n - 1, -1, -1):
        min_size = inf
        min_pos = -1
        
        
        for sz, p in zip(size, pos):
            if sz < min_size:
                min_size = sz
                min_pos = p
        code = ord(s[i]) - 97
        size[code] = min_size + 1
        pos[code] = i
        nxt[i] = min_pos
        
        
        
        
    
    min_size = inf
    min_pos = -1
    for sz, p in zip(size, pos):
        if sz < min_size:
            min_size = sz
            min_pos = p
    i = min_pos
    ans = s[i]
    while i < n:
        i = nxt[i]
        ans += s[i]
    print(ans)

main()

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

S = sys.stdin.readline().rstrip()
A = [ord(c) - ord('a') for c in S]
N = len(S)


l = 0

lengths = [0] * N
counts = [0] * 26
for i, a in reversed(list(enumerate(A))):
    counts[a] += 1
    lengths[i] = l
    if min(counts) == 1:
        counts = [0] * 26
        l += 1
ans_size = l + 1


graph = [[-1] * 26 for _ in range(N)]
pos = [-1] * 26
for i, a in reversed(list(enumerate(A))):
    graph[i] = pos[:]
    pos[a] = i
initials = pos


def solve(size, i=None):
    
    if i is None:
        pos = initials
    else:
        pos = graph[i]

    if size == 1:
        return chr(pos.index(-1) + ord('a'))

    size -= 1
    for ci, i in enumerate(pos):
        if lengths[i] < size:
            c = chr(ci + ord('a'))
            return c + solve(size, i)
    assert False


print(solve(ans_size))

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

S = sys.stdin.readline().rstrip()
A = [ord(c) - ord('a') for c in S]
N = len(S)


l = 0

lengths = [0] * N
counts = [0] * 26
for i, a in reversed(list(enumerate(A))):
    counts[a] += 1
    lengths[i] = l
    if min(counts) == 1:
        counts = [0] * 26
        l += 1
ans_size = l + 1


graph = [[-1] * 26 for _ in range(N)]
pos = [-1] * 26
for i, a in reversed(list(enumerate(A))):
    graph[i] = pos[:]
    pos[a] = i
initials = pos


def solve(size, i=None):
    
    if i is None:
        pos = initials
    else:
        pos = graph[i]

    if size == 1:
        return chr(pos.index(-1) + ord('a'))

    size -= 1
    for ci, i in enumerate(pos):
        if lengths[i] < size:
            c = chr(ci + ord('a'))
            return c + solve(size, i)
    return ''


print(solve(ans_size))

Solution (Python):
def main():
    import sys
    input=sys.stdin.readline
    s=input()
    alpha="abcdefghijklmnopqrstuvwxyz"
    l=len(s)
    alpha2={j:i for i,j in enumerate(alpha)}
    memo=[[0]*26 for _ in range(l,-1,-1)]
    for i in range(26):
        memo[l][i]=l+1
    for i in range(l-1,-1,-1):
        for x,y in alpha2.items():
            if s[i]==x:
                memo[i][y]=i+1
            else:
                memo[i][y]=memo[i+1][y]
    
    search=[1]*(l+2)
    search[l+1]=0
    for i in range(l-1,-1,-1):
        m=max([memo[i][j] for j in range(26)])
        if m!=l+1:
            search[i]=search[m]+1
    
    n,seq=0,0
    ans_len=search[0]
    ans=""
    temp=0
    for i in range(ans_len):
        for j in range(26):
            n=memo[temp][j]
            seq=search[n]+i
            if seq+1==ans_len:
                ans+=alpha[j]
                temp=memo[temp][j]
                break
    print(ans)
if __name__=='__main__':
    main()

Solution (Python):
def main():
    import sys
    input=sys.stdin.readline
    s=input()
    alpha="abcdefghijklmnopqrstuvwxyz"
    l=len(s)
    alpha2={j:i for i,j in enumerate(alpha)}
    memo=[[0]*26 for _ in range(l,-1,-1)]
    for i in range(26):
        memo[l][i]=l+1
    for x,y in alpha2.items():
        for i in range(l-1,-1,-1):
            if s[i]==x:
                memo[i][y]=i+1
            else:
                memo[i][y]=memo[i+1][y]
    
    search=[1]*(l+2)
    search[l+1]=0
    for i in range(l-1,-1,-1):
        m=max([memo[i][j] for j in range(26)])
        if m!=l+1:
            search[i]=search[m]+1
    
    n,seq=0,0
    ans_len=search[0]
    ans=""
    temp=0
    for i in range(ans_len):
        for j in range(26):
            n=memo[temp][j]
            seq=search[n]+i
            if seq+1==ans_len:
                ans+=alpha[j]
                temp=memo[temp][j]
                break
    print(ans)
if __name__=='__main__':
    main()

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

S = input()
N = len(S)


nxt = list2d(N+1, 26, N)
for i in range(N-1, -1, -1):
    for c in range(26):
        nxt[i][c] = nxt[i+1][c]
    c = ord(S[i]) - 97
    nxt[i][c] = i


dp = [INF] * (N+1)

rest = [None] * (N+1)
dp[N] = 1

for i in range(N-1, -1, -1):
    
    
    for c in range(26):
        
        if nxt[i][c] == N:
            if dp[i] > 1:
                dp[i] = 1
                rest[i] = (c, N)
        
        else:
            
            
            if dp[i] > dp[nxt[i][c]+1] + 1:
                dp[i] = dp[nxt[i][c]+1] + 1
                rest[i] = (c, nxt[i][c]+1)


i = 0
ans = []
while i < N:
    c, idx = rest[i]
    ans.append(chr(c+97))
    i = idx
print(''.join(ans))