AtCoder Regular Contest 081 - Don't Be a Subsequence

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: HARD

Starter code:

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


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


def main():
	import sys
	input = sys.stdin.readline
	a = list(input())[:-1]
	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])
main()


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


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


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


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)


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


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


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([])
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]
		for i in range(26):
			if loc_list_last[n][i] <= loc:
				ans.append(i)
				mozi = i
				break
ans2 = []
for i in range(len(ans)):
	ans2.append(num2alpha(ans[i] + 1))
print(''.join(ans2))


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


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


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


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


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


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


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


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


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


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


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 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)
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
for j in range(26):
	if K[j][t] == N:
		ans += alpha[j]
		break
print(ans)


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

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


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


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


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)


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()
ans = [history[0]]
for (i, a) in enumerate(A):
	if ans[-1] == a:
		ans.append(history[i])
print(''.join(ans))


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


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


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


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)


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 next_position(S):
	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))


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)


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)


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)


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


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


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


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


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


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


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


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)


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


abc = 'abcdefghijklmnopqrstuvwxyz'
A = str(input())
n = len(A)
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:
		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
		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)


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


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