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-----
atcoderregularcontest

-----Sample Output-----
b

The string atcoderregularcontest contains a as a subsequence, but not b.

Difficulty: competition

Starter code:

Solutions:
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]))

from collections import *

def solve():
    s = input()
    n = len(s)
    nxt = [[float("inf")] * (n + 10) for _ in range(26)]
    for i in range(n - 1, -1, -1):
        for j in range(26):
            nxt[j][i] = nxt[j][i + 1]
        nxt[ord(s[i]) - ord('a')][i] = i 
    deq = deque()
    used = [False] * (n + 5)
    for i in range(26):
        if nxt[i][0] == float("inf"):
            print((chr(ord('a') + i)))
            return 
        deq.append((i, str(chr(ord('a') + i)), nxt[i][0]))
        used[nxt[i][0]]  = True 
    while True:
        siz = len(deq)
        for _ in range(siz):
            i, pre, pos = deq.popleft()
            for j in range(26):
                np = nxt[j][pos + 1]
                if np == float("inf"):
                    print((pre + str(chr(ord('a') + j))))
                    return 
                if not used[np]:
                    used[np] = True 
                    deq.append((j, pre + str(chr(ord('a') + j)), np))

solve()


import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    a = S()
    l = len(a)
    t = {}
    for c in string.ascii_lowercase:
        t[c] = l
    b = [(1,0,0) for _ in range(l)]
    b.append((1,'a',l))
    b.append((0,'',l+1))

    for c,i in reversed(list(zip(a,list(range(l))))):
        t[c] = i
        b[i] = min([(b[t[d]+1][0] + 1,d,t[d]+1) for d in string.ascii_lowercase])

    r = ''
    i = 0
    while i < l:
        r += b[i][1]
        i = b[i][2]
    return r

print((main()))





# -*- coding: utf-8 -*-

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 list(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[i][c] := i文字目以降で最初に文字cが登場するindex(存在しないときはN)
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[i] := i文字目以降について「部分文字列とならない」最短の文字列長
dp = [INF] * (N+1)
# rest[i][(c, j)] := 位置iから見て、最小達成に用いた文字cと、次に使う文字のindexj
rest = [None] * (N+1)
dp[N] = 1
# 常に自分より後ろでの最小が必要になるので、後ろから埋めていく
for i in range(N-1, -1, -1):
    # iから見て先頭として使う文字を26通り全部試す
    # abcを昇順で回して、最小更新条件を等号なしにすることで、辞書順で小さい方を優先できる
    for c in range(26):
        # 次の文字がない時
        if nxt[i][c] == N:
            if dp[i] > 1:
                dp[i] = 1
                rest[i] = (c, N)
        # 次の文字がある時
        else:
            # i以降に文字cが出現するindex+1の位置での最短文字列長 + 1
            # 例えばaについてなら、a****となるので、****での最小とaの分で+1
            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)))


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 = '')



    
        





import bisect
A = input()
n = len(A)
ch = [[] for _ in range(26)]
idx = []
used = set()
for i in range(n-1, -1, -1):
  a = A[i]
  ch[ord(a)-ord("a")].append(i)
  used.add(a)
  if len(used) == 26:
    idx.append(i)
    used = set()
k = len(idx)
idx = idx[::-1]
for j in range(26):
  ch[j] = ch[j][::-1]
ans = ""
now = -1
for i in range(k):
  for j in range(26):
    nxt = ch[j][bisect.bisect_right(ch[j], now)]
    if nxt >= idx[i]:
      now = nxt
      ans += chr(j+ord("a"))
      break
for j in range(26):
  l = bisect.bisect_right(ch[j], now)
  if l == len(ch[j]):
    ans += chr(j+ord("a"))
    break
print(ans)

from bisect import bisect
s = input()
x,y,k,p = [1]*26,[len(s)],1,[[1] for i in range(26)]
for i in range(len(s)-1,-1,-1):
	n = ord(s[i])-97
	x[n] = 0
	p[n].append(-i)
	if sum(x)==0:
		k,x = k+1,[1]*26
		y.append(i)
y,num,ans = y[::-1],0,""
for i in range(k):
	for j in range(97,123):
		if chr(j) not in s[num:y[i]]: break
	ans+=chr(j)
	b = bisect(p[j-97],-y[i])-1
	num = -p[j-97][b]+1
print(ans)

S = input()
N = len(S)
inf = 10**18

nxt = [[N+1] * 26 for _ in range(N + 2)]
for i in reversed(range(N)):
    for j in range(26):
        nxt[i][j] = nxt[i + 1][j]
    nxt[i][ord(S[i]) - ord("a")] = i

dp = [inf] * (N + 1)
dp[N] = 1
memo = [N] * (N + 1)
for i in reversed(range(N)):
    for c, j in enumerate(nxt[i]):
        if j > N:
            if dp[i] > 1:
                dp[i] = 1
                memo[i] = c
        elif dp[i] > dp[j + 1] + 1:
            dp[i] = dp[j + 1] + 1
            memo[i] = c

res = []
i = 0
while i <= N:
    res.append(chr(memo[i] + ord("a")))
    i = nxt[i][memo[i]] + 1
print("".join(res))

import sys
input = sys.stdin.readline

S = [ord(s) - ord('a') for s in input().rstrip()]

INF = 10 ** 9
N = len(S)
dp = [None] * (N+1)
# そこから始めたとき、次にxが現れる位置、および、次にxをとった場合に長さLのものが全て作れる
dp[N] = [[INF] * 26, [0] * 26, 0]

for n in range(N-1,-1,-1):
    prev = dp[n+1]
    cur = [prev[0].copy(), prev[1].copy(), prev[2]]
    s = S[n]
    cur[0][s] = n
    cur[1][s] = prev[2] // 26 + 1
    cur[2] = prev[2] + cur[1][s] - prev[1][s]
    dp[n] = cur

answer = []
i = 0
while i < N:
    # 辞書順で、作れる長さが一番短い文字
    L = dp[i][2] // 26
    for x in range(26):
        if dp[i][1][x] == L:
            break
    answer.append(chr(ord('a') + x))
    # その文字の場所に移動
    i = dp[i][0][x]
    i += 1

print(''.join(answer))

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)
    return

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)


def next_position(S):
    """
    閉区間 (i,N-1] の中の最も左端にあるアルファベットsのindex
    """
    N=len(S)
    next_pos=[[N+1]*26 for _ in range(N+1)]
    for i in range(N-1,-1,-1):
        for s in range(26):
            next_pos[i][s]=next_pos[i+1][s]
        next_pos[i][ord(S[i])-ord("a")]=i+1
    return next_pos

S=input().rstrip()
N=len(S)
next_pos=next_position(S)
dp=[1<<32]*(N+2)
dp[-1]=0
recover=[0]*(N+1)
for i in range(N,-1,-1):
    for s in range(25,-1,-1):
        if dp[next_pos[i][s]]+1<=dp[i]:
            dp[i]=dp[next_pos[i][s]]+1
            recover[i]=(next_pos[i][s],s)

res=[]
i=0
while i<N:
    i,s=recover[i]
    res.append(chr(s+ord("a")))
print("".join(res))

abc="abcdefghijklmnopqrstuvwxyz"

A=str(input())
n=len(A)
#make matrix (a-z)*(n characters)
#次にchrが出てくるindex
word_pos=[]
ct=[n]*26
orda=ord("a")

for i in range(n-1,-1,-1):
    ct[ord(A[i])-orda]=i
    word_pos.append(ct.copy())

word_pos.reverse()

dp=[0]*n+[1,0]
j=n
sep=[]
#区切れめをマーク
for i in range(n-1,-1,-1):
    ct=word_pos[i]
    if(max(ct)<j):
        #remove last chunk
        sep.append(i)
        j=min(ct)
        
if(j==n):
    for i in abc:
        if(i not in A):
            print(i+"\n")
            break

else:
    sep.reverse()
    ans=""
    for i in abc:
        if(i not in A[:sep[0]]):
            ans+=i
            break

    for i in range(0,len(sep)):
        start=sep[i]
        try:
            end=sep[i+1]
        except:
            end=n
        #ans[-1]が出現するタイミング
        next=word_pos[start][ord(ans[-1])-orda]
        for i in range(0,26):
            if(word_pos[next+1][i]>end-1):
                ans+=chr(orda+i)
                break
    ans+="\n"
    print(ans)

# import sys
from sys import stdout
# from copy import copy, deepcopy
# from functools import lru_cache
# from string import ascii_lowercase
# from math import inf
# inf = float('inf')


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[from_idx][letter_idx] := the position of the next letter `letter_idx` from `from_idx`
    next_char_pos = make_list((len_s + 1, 26), len_s)
    for from_idx in reversed(list(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[from_idx] := the length of the shortest "non subsequence" in S[from_idx:]
    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(list(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
# shape: tuple of ints | list of ints
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])]

def __starting_point():
    # sys.setrecursionlimit(1000000)
    main()

__starting_point()

#!/usr/bin/env python3

def main():
    A = input()

    n = len(A)

    next_i = []
    ct = [n] * 26
    orda = ord("a")
    for i in range(n - 1, -1, -1):
        ct[ord(A[i]) - orda] = i
        next_i.append(ct.copy())

    next_i.reverse()

    dp = [0] * (n + 1)
    dp[n] = 1
    j = -1
    for i in range(n - 1, -1, -1):
        ct = next_i[i]
        if max(ct) < n:
            j = i
            break
        else:
            dp[i] = 1

    if j == -1:
        ct = next_i[0]
        for c in range(26):
            if ct[c] == n:
                print((chr(orda + c)))
                return

    rt = [0] * n
    for i in range(j, -1, -1):
        ct = next_i[i]
        min_c = 0
        min_v = dp[ct[0] + 1]
        for c in range(1, 26):
            v = dp[ct[c] + 1]
            if v < min_v:
                min_c = c
                min_v = v
        rt[i] = min_c
        dp[i] = min_v + 1


    r = ''
    i = 0
    while i < n:
        if dp[i] == 1:
            for c in range(26):
                if not chr(orda + c) in A[i:]:
                    r += chr(orda + c)
                    break
            break
        r += chr(orda + rt[i])
        i = next_i[i][rt[i]] + 1


    print(r)


def __starting_point():
    main()


__starting_point()

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

    # next[i][c] : i 文字目以降で c が現れる最小の index
    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[i] : S[i:] に対する答えの長さ
    dp = [INF] * (n + 1)
    dp[n] = 1
    # character[i] : S[i:] に対する答えに対して採用する先頭の文字
    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()

# import sys
from sys import stdout
# from copy import copy, deepcopy
# from functools import lru_cache
# from string import ascii_lowercase
# from math import inf
# inf = float('inf')


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[from_idx][letter_idx] := the position of the next letter `letter_idx` from `from_idx`
    next_char_pos = make_list((len_s + 1, 26), len_s)
    for from_idx in reversed(list(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[from_idx] := the length of the shortest "non subsequence" in S[from_idx:]
    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(list(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
# shape: tuple of ints | list of ints
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])]

def __starting_point():
    # sys.setrecursionlimit(1000000)
    main()

__starting_point()

A = input()

import string
p = {}
for x in string.ascii_lowercase: p[x] = len(A)
tb = [(0, 0, 0)] * len(A)
tb.append((1, 0, 0))
tb.append((0, 0, 0))

for i, x in reversed(list(enumerate(A))):
    p[x] = i
    tb[i] = min([(tb[p[c]+1][0] + 1, c, p[c]+1) for c in string.ascii_lowercase])

i = 0
ans = []
while i < len(A):
    ans.append(tb[i][1])
    i = tb[i][2]

print(("".join(ans)))


from collections import deque

As = input()

As = [ord(A) - ord('a') for A in As]
lenA = len(As)
posChars = [lenA] * 26
posNexts = [[] for _ in range(lenA + 1)]
for i in reversed(list(range(lenA))):
    posNexts[i + 1] = posChars.copy()
    posChars[As[i]] = i
posNexts[0] = posChars.copy()

prevs = [None] * lenA
Q = deque()
Q.append((0, -1))
while Q:
    lenAns, pos = Q.popleft()
    for ch in range(26):
        posNext = posNexts[pos + 1][ch]
        if posNext == lenA:
            ans = [chr(ord('a') + ch)]
            while pos != -1:
                ans.append(chr(ord('a') + As[pos]))
                pos = prevs[pos]
            print((''.join(reversed(ans))))
            return
        if prevs[posNext] is None:
            prevs[posNext] = pos
            Q.append((lenAns + 1, posNext)) 


S = input()
N = len(S)
inf = 10**18

nxt = [[N+1] * 26 for _ in range(N + 2)]
for i in reversed(range(N)):
    for j in range(26):
        nxt[i][j] = nxt[i + 1][j]
    nxt[i][ord(S[i]) - ord("a")] = i

dp = [inf] * (N + 1)
dp[N] = 1
memo = [N] * (N + 1)
for i in reversed(range(N)):
    for c, j in enumerate(nxt[i]):
        if j > N:
            if dp[i] > 1:
                dp[i] = 1
                memo[i] = c
        elif dp[i] > dp[j + 1] + 1:
            dp[i] = dp[j + 1] + 1
            memo[i] = c

res = []
i = 0
while i <= N:
    res.append(chr(memo[i] + ord("a")))
    i = nxt[i][memo[i]] + 1
print("".join(res))

import string

def __starting_point():
    A = input()

    p = {}
    for x in string.ascii_lowercase:
        p[x] = len(A)
    # print(p)
    '''
    tb
    1つ目：
    2つ目：アルファベット
    3つ目：
    '''
    tb = [(0, 0, 0)] * len(A)
    tb.append((1, 0, 0))
    tb.append((0, 0, 0))
    # print(tb)
    for i, x in reversed(list(enumerate(A))):
        p[x] = i
        tb[i] = min([(tb[p[c] + 1][0] + 1, c, p[c] + 1) for c in string.ascii_lowercase])
        # print(tb)
    i = 0
    ans = []
    while i < len(A):
        ans.append(tb[i][1])
        i = tb[i][2]

    print(("".join(ans)))

__starting_point()

import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
S = list(map(lambda x: ord(x) - ord("a"), list(input())[: -1]))
table = [[] for _ in range(26)]
for i in range(len(S)):
  x = S[i]
  table[x].append(i + 1)
for c in range(26): table[c].append(len(S) + 1)
dp = [len(S)] * (len(S) + 2)
dp[-1] = 0
rev = [0] * (len(S) + 1)
revc = [0] * (len(S) + 1)
for i in range(len(S) - 1, -1, -1):
  for x in range(26):
    j = table[x][bl(table[x], i + 1)]
    if dp[i] > dp[j] + 1:
      dp[i] = dp[j] + 1
      rev[i] = j
      revc[i] = x
      #print(i, x, j, table[x])
x = 0
res = []
while x < len(S):
  c = revc[x]
  res.append(chr(c + ord("a")))
  if x == len(S): break
  x = rev[x]
print("".join(res))

A = '.' + input()

smallalphas = list(map(chr, list(range(ord("a"), ord("z") + 1))))

answers = {c: 0 for c in smallalphas}
last_ch = 'a'
history = []
for a in reversed(A):
    ch = 'a'
    for c in smallalphas:
        if answers[ch] > answers[c]:
            ch = c
    answers[a] = answers[ch] + 1
    history.append(ch)

history.reverse()

# print(history)

ans = [history[0]]
for i, a in enumerate(A):
    if ans[-1] == a:
        ans.append(history[i])

print((''.join(ans)))
# minlen = min(map(len, answers))
# ans = min(filter(lambda ans: len(ans) == minlen, answers))
# print(ans)


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())))


a = list([ord(x)-ord("a") for x in list(input())])
n = len(a)
m = 26

b = [0]*n
pos = [[] for i in range(m)]
s = set()
cnt = 0
for i in reversed(list(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)


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

    a = list(input())[:-1]
    #print(a)
    n = len(a)

    d = dict()
    for i in range(26):
        d[chr(i+97)] = chr(i+97)
    

    for i in range(n-1,-1,-1):
        min_key = 'zz'
        min_len = 10**9
        for e in d:
            if (min_len == len(d[e]) and min_key > e) or (min_len > len(d[e])):
                min_key = e
                min_len = len(d[e])
        d[a[i]] = a[i]+d[min_key]

    res_len = len(d['a'])
    res_key = 'a'
    for e in d:
        if (res_len == len(d[e]) and res_key > e) or (res_len > len(d[e])):
            res_key = e
            res_len = len(d[e])
    print(d[res_key])

def __starting_point():
    main()
__starting_point()

import sys
input = sys.stdin.readline

a = list(input().rstrip())
n = len(a)
x = [[0] * 26 for _ in range(n + 1)]
for i in range(n):
    j = ord(a[i]) - 97
    x[i][j] = i + 1
for i in range(n - 1, -1, -1):
    for j in range(26):
        if x[i][j] == 0:
            x[i][j] = x[i + 1][j]
minlen = [0] * (n + 1)
minalph = [0] * (n + 1)
for i in range(n - 1, -1, -1):
    l = 114514
    for j in range(26):
        if x[i][j] == 0:
            l, m = 0, j
            break
        if l > minlen[x[i][j]] + 1:
            l, m = minlen[x[i][j]] + 1, j
    minlen[i] = l
    minalph[i] = m
ans = []
i = 0
for _ in range(minlen[0] + 1):
    ans.append(chr(minalph[i] + 97))
    i = x[i][minalph[i]]
ans = "".join(ans)
print(ans)

A=input()
N=len(A)
alphabet=["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"]
alp_to_n={}
for i,l in enumerate(alphabet):
  alp_to_n[l]=i
  
D=[True]*26
L=[N]
s=0
for i in range(N)[::-1]:
  if D[alp_to_n[A[i]]]:
    D[alp_to_n[A[i]]]=False
    s+=1
  if s==26:
    D=[True]*26
    L.append(i)
    s=0
L.reverse()
ans=[]
D=[True]*26
for i in range(0,L[0]):
    D[alp_to_n[A[i]]]=False
    
for i in range(len(L)-1):
  num,pos=26,0
  for j in range(L[i],L[i+1]):
    if alp_to_n[A[j]]<num and D[alp_to_n[A[j]]]:
      num=alp_to_n[A[j]]
      pos=j
  ans.append(alphabet[num])
  D=[True]*26
  for j in range(pos+1,L[i+1]):
    D[alp_to_n[A[j]]]=False
for i in range(26):
  if D[i]:
    ans.append(alphabet[i])
    break
print(("".join(ans)))
  
      
  


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 = '')



    
        





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)))

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))

from copy import copy
from collections import deque
import sys
A = input()
N = len(A)
M = 26

def alp(c):
  return chr(ord("a")+c)
def num(s):
  return ord(s)-ord("a")
  

INF = 10**6
tmp = [INF for _ in range(M)]
Nxt = [None for _ in range(N+1)]
Nxt[N] = copy(tmp)
for i in range(N-1,-1,-1):
  tmp[num(A[i])] = i+1
  Nxt[i] = copy(tmp)
#print(*Nxt, sep = "\n")  
task = deque([(0, "")])
visited = {0}
  
while task:
  i, s = task.popleft()
  for c, j in enumerate(Nxt[i]):
    if j == INF:
      print("".join([s,alp(c)]))
      return
    if j not in visited:
      task.append((j, "".join([s,alp(c)])))
      visited.add(j)
    
print("error")

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)

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))
    # print(s)
    # 次をその文字にした時の「長さ、位置」
    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
        # print(size)
        # print(pos)
        # print(nxt)
        # print()
    # 最短になる最初の文字を調べて、nxtの順にたどる
    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()


from collections import deque
alpha = "abcdefghijklmnopqrstuvwxyz"
A = input()
n = len(A)
B = ord('a')

links = [None]*(n+3)

link = [n]*26
for i in range(n-1, -1, -1):
    links[i] = link[:]
    link[ord(A[i]) - B] = i
links[-1] = link

deq = deque()
deq.append(-1)
prev = {-1: (None, 0)}
while deq:
    v = deq.popleft()
    if v == n:
        break
    link = links[v]
    for c in range(26):
        if link[c] in prev:
            continue
        prev[link[c]] = (v, c)
        deq.append(link[c])
v = n
ans = []
while v is not None:
    v, c = prev[v]
    ans.append(chr(c+B))
ans.reverse()
print(("".join(ans[1:])))



from bisect import bisect_left

CHARACTERs = 'abcdefghijklmnopqrstuvwxyz'

As = input()
lenA = len(As)

posChars = dict([(ch, [lenA]) for ch in CHARACTERs])
dp = [0] * lenA + [1, 0]
for i in reversed(list(range(lenA))):
    posChars[As[i]].append(i)
    dp[i] = min([dp[posChars[ch][-1] + 1] for ch in CHARACTERs]) + 1

for ch in CHARACTERs:
    posChars[ch] = posChars[ch][::-1]

ans = []
i = 0
for k in reversed(list(range(dp[0]))):
    for ch in CHARACTERs:
        pos = posChars[ch][bisect_left(posChars[ch], i)]
        if dp[pos + 1] == k:
            ans.append(ch)
            i = pos + 1
            break

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


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))

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)
def __starting_point():
    main()
__starting_point()

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n, = map(int,readline().split())
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])
"""

#print(nxt)
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

#print(nxt[0])
#print(dp)

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

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

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

#print(ans)
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)
"""














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):
    # i 番目から始まり、長さ size である、部分列でない文字列
    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)))


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)
def __starting_point():
    main()
__starting_point()

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))

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]))

from collections import Counter
s = input()
def num(letter):
	return ord(letter) - 97
def let(number):
	return chr(number + 97)

ok = 0
ng = len(s)
used = [False] * 26
tmp = 0
cnt = 0
for i in range(len(s)):
	if used[num(s[i])] == False:
		used[num(s[i])] = True
		tmp += 1
	if tmp == 26:
		cnt += 1
		tmp = 0
		used = [False] * 26

prm = cnt+1

if prm == 1:
	for j in range(26):
		if used[j] == False:
			print(let(j))
			break
else:
	d = []
	used = [False] * 26
	tmp = 0
	for i in range(len(s)-1, -1, -1):
		if used[num(s[i])] == False:
			used[num(s[i])] = True
			tmp += 1
		if tmp == 26:
			tmp = 0
			used = [False] * 26
			d.append(i)
	d = d[::-1]
	ans = ""
	cnt = 0
	i = 0
	skip = False
	used = [False] * 26
	for i in range(len(s)):
		if cnt < prm-1:
			if i == d[cnt]:
				for j in range(26):
					if used[j] == False:
						ans += let(j)
						break
				used = [False] * 26
				cnt += 1
				skip = True			
		if skip:
			if s[i] == ans[-1]:
				skip = False
			continue
		if used[num(s[i])] == False:
			used[num(s[i])] = True

	for j in range(26):
		if used[j] == False:
			ans += let(j)
			break
	print(ans)

S=input()
N=len(S)
a=ord('a')
alpha=['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']
K=[[N]*(N+1) for i in range(26)]
for i in range(N-1,-1,-1):
    x=ord(S[i])-a
    for j in range(26):
        if j==x:
            K[j][i]=i
            continue
        K[j][i]=K[j][i+1]
dp=[0]*(N+2)
L=[0]*(N+2)
dp[N]=1
for i in range(N-1,-1,-1):
    c=0
    b=2*N
    for j in range(26):
        t=K[j][i]
        if b>dp[t+1]+1:
            b=dp[t+1]+1
            c=t+1
    dp[i]=b
    L[i]=c
X=dp[0]
t=0
ans=''
while X>1:
    t=L[t]
    ans+=S[t-1]
    X-=1
    #print(t,X,ans)
for j in range(26):
    if K[j][t] ==N:
        ans+=alpha[j]
        break
print(ans)




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))
      return
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


def main():
    # import sys
    # readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    
    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)

    # k =
    # for j in range(26):
    #     ni = na[0][j]
    #     if dp[i] > dp[ni] + 1:

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

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


def __starting_point():
    main()

__starting_point()

from itertools import accumulate

S = list(map(ord, input().strip()))
N = len(S)

atype = set()
seg = [0]*N
seg[-1] = 1
for i in range(N-1, -1, -1):
    atype.add(S[i])
    if len(atype) == 26:
        atype = set()
        seg[i] = 1

inf = 1<<32
idx = [[inf]*N for _ in range(26)]
for i in range(N-1, -1, -1):
    s = S[i] - 97
    idx[s][i] = i

for s in range(26):
    for i in range(N-2, -1, -1):
        idx[s][i] = min(idx[s][i], idx[s][i+1])



seg = list(accumulate(seg[::-1]))[::-1]
seg.append(1)
L = seg[0]
ans = []
cnt = -1
for i in range(L):
    for c in range(26):
        k = idx[c][cnt+1]
        if k == inf:
            ans.append(97+c)
            break
        if seg[k+1] + i + 1 <= L:
            ans.append(97+c)
            cnt = k
            break
        

print(''.join(map(chr, ans)))

from collections import Counter
s = input()
def num(letter):
	return ord(letter) - 97
def let(number):
	return chr(number + 97)

ok = 0
ng = len(s)
used = [False] * 26
tmp = 0
cnt = 0
for i in range(len(s)):
	if used[num(s[i])] == False:
		used[num(s[i])] = True
		tmp += 1
	if tmp == 26:
		cnt += 1
		tmp = 0
		used = [False] * 26

prm = cnt+1

if prm == 1:
	for j in range(26):
		if used[j] == False:
			print(let(j))
			break
else:
	d = []
	used = [False] * 26
	tmp = 0
	for i in range(len(s)-1, -1, -1):
		if used[num(s[i])] == False:
			used[num(s[i])] = True
			tmp += 1
		if tmp == 26:
			tmp = 0
			used = [False] * 26
			d.append(i)
	d = d[::-1]
	#print(d)
	ans = ""
	cnt = 0
	i = 0
	skip = False
	used = [False] * 26
	for i in range(len(s)):
		if cnt < prm-1:
			if i == d[cnt]:
				for j in range(26):
					if used[j] == False:
						ans += let(j)
						break
				used = [False] * 26
				cnt += 1
				skip = True
				
		if skip:
			if s[i] == ans[-1]:
				#print(i)
				skip = False
			continue

		if used[num(s[i])] == False:
			used[num(s[i])] = True

	#print(used)
	for j in range(26):
		if used[j] == False:
			ans += let(j)
			break
	print(ans)

import bisect
A = input()
n = len(A)
ch = [[] for _ in range(26)]
idx = []
used = set()
for i in range(n-1, -1, -1):
  a = A[i]
  ch[ord(a)-ord("a")].append(i)
  used.add(a)
  if len(used) == 26:
    idx.append(i)
    used = set()
k = len(idx)
idx = idx[::-1]
for j in range(26):
  ch[j] = ch[j][::-1]
ans = ""
now = -1
for i in range(k):
  for j in range(26):
    nxt = ch[j][bisect.bisect_right(ch[j], now)]
    if nxt >= idx[i]:
      now = nxt
      ans += chr(j+ord("a"))
      break
for j in range(26):
  l = bisect.bisect_right(ch[j], now)
  if l == len(ch[j]):
    ans += chr(j+ord("a"))
    break
print(ans)


"""
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):

    #print ("".join(A[:nind]))

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

    nind = lastap[nind][minind]-1

#ans.reverse()
print ("".join(ans))

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])))
            return
    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))))



def __starting_point():
    main()

__starting_point()

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))


ord_a = ord('a')
L = 26

S = list(map(lambda c: ord(c)-ord_a,input()))


memo = []

f = [0]*L
cnt = 0


for i,s in zip(reversed(range(len(S))),reversed(S)):

  cnt += (f[s] == 0)
  f[s] += 1
  if cnt == L:
    memo.append((i,f))
    f = [0]*L
    cnt = 0


result = [f.index(0)]

for i,f in reversed(memo):
  c = result[-1]
  for j in range(i,len(S)):
    s = S[j]
    f[s] -= 1
    if s == c:
      break

  result.append(f.index(0))

print(''.join(map(lambda x: chr(x+ord_a), result)))

from collections import deque
alpha = "abcdefghijklmnopqrstuvwxyz"
A = input()
n = len(A)
B = ord('a')

links = [None]*(n+3)

link = [n]*26
for i in range(n-1, -1, -1):
    links[i] = link[:]
    link[ord(A[i]) - B] = i
links[-1] = link

deq = deque()
deq.append(-1)
prev = {-1: (None, 0)}
while deq:
    v = deq.popleft()
    if v == n:
        break
    link = links[v]
    for c in range(26):
        if link[c] in prev:
            continue
        prev[link[c]] = (v, c)
        deq.append(link[c])
v = n
ans = []
while v is not None:
    v, c = prev[v]
    ans.append(chr(c+B))
ans.reverse()
print(("".join(ans[1:])))



n2a=lambda x:chr(x+ord('a'))
a2n=lambda x:ord(x)-ord('a')

def main(a):
  nc=26
  n=len(a)
  ary=[]
  tmp=[0]*nc
  mi=set(range(nc))
  for i in range(n-1,-1,-1):
    x=a2n(a[i])
    mi.discard(x)
    tmp[x]+=1
    if len(mi)==0:
      ary.append(tmp.copy())
      tmp=[0]*nc
      mi=set(range(nc))
  if any(tmp):ary.append(tmp)
  #for x in ary:print(x)
  ans=[]
  now=0
  tmp=ary.pop()
  if all(tmp):
    ans.append('a')
    while a[now]!='a':
      tmp[a2n(a[now])]-=1
      now+=1
    tmp[a2n(a[now])]-=1
    now+=1
  else:
    for i in range(nc):
      if tmp[i]==0:
        ans.append(n2a(i))
        break
    if not ary:return ans
    ntmp=ary.pop()
    for j in range(nc):tmp[j]+=ntmp[j]
    while a2n(a[now])!=i:
      tmp[a2n(a[now])]-=1
      now+=1
    tmp[a2n(a[now])]-=1
    now+=1
  while True:
    #print(ary,tmp,ans)
    for i in range(nc):
      if tmp[i]==0:
        ans.append(n2a(i))
        break
    if not ary:return ans
    ntmp=ary.pop()
    for j in range(nc):tmp[j]+=ntmp[j]
    while a2n(a[now])!=i:
      tmp[a2n(a[now])]-=1
      now+=1
    tmp[a2n(a[now])]-=1
    now+=1

a=input()
print(*main(a),sep='')
"""
bcdefghijklmnopqrstuvwxyza

aabbccaabca
aab / bccaa / bca

"""



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)

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):
    # i 番目から始まり、長さ size である、部分列でない文字列
    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)))



import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()

alpha2num = lambda c: ord(c) - ord('a')


def num2alpha(num):
	if num<=26:
		return chr(96+num)
	elif num%26==0:
		return num2alpha(num//26-1)+chr(122)
	else:
		return num2alpha(num//26)+chr(96+num%26)

A = input()

loc_list = deque([])
loc_list_last = deque([])
num = 0
alpha_list = [-1] * 26
alpha_list_last = [-1] * 26
roop = 0
for i in range(len(A) - 1, -1, -1):
	alphanum = alpha2num(A[i])
	if alpha_list[alphanum] == -1:
		num += 1
		alpha_list_last[alphanum] = i
	alpha_list[alphanum] = i
	if num == 26:
		loc_list.appendleft(alpha_list)
		loc_list_last.appendleft(alpha_list_last)
		alpha_list = [-1]*26
		alpha_list_last = [-1]*26
		roop += 1
		num = 0
loc_list.appendleft(alpha_list)
loc_list_last.appendleft(alpha_list_last)
ans = deque([])
#print(loc_list)
for i in range(26):
	if loc_list[0][i] == -1:
		x = i
		ans.append(x)
		break

if len(loc_list) > 1:
	mozi = x
	for n in range(1, len(loc_list)):
		loc = loc_list[n][mozi]
		#print(loc, mozi)
		for i in range(26):
			if loc_list_last[n][i] <= loc:
				ans.append(i)
				mozi = i
				break
#print(loc_list)

ans2 = []

for i in range(len(ans)):
	ans2.append(num2alpha(ans[i] + 1))
print(''.join(ans2))

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))
            return
        if dp[i] == dp[next_[char][i]] + 1:
            ans.append(alph[char])
            i = next_[char][i]
            break

from bisect import bisect_left
A = input()

N = len(A)
dp = [0] * (N + 2)
dp[N] = 1
d = [[N] for i in range(26)]
a = ord('a')
INF = float('inf')
for i in range(N - 1, -1, -1):
    d[ord(A[i]) - a].append(i)
    tmp = INF
    for j in range(26):
        tmp = min(tmp, dp[d[j][-1] + 1])
    dp[i] = tmp + 1


for i in range(26):
    d[i] = d[i][::-1]

pos = 0
ans = ''
for i in range(dp[0] - 1, -1, -1):
    for j in range(26):
        k = bisect_left(d[j], pos)
        if dp[d[j][k] + 1] == i:
            ans += chr(j + a)
            pos = d[j][k] + 1
            break

print(ans)


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  # 文字cの直後の頂点


recon = [None] * (N + 2)  # DP復元用。(直前の頂点, 文字)を格納する。
q = deque()
q.append(0)  # 頂点
while q:
    i = q.popleft()
    if i == N + 1:  # 頂点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))))


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)に含まれない文字のうちの最小
    """
#     print(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)
# else:
#     ans = "a" * (len(l)+1)
print(ans)