Problem:


Score : 600 points

Problem Statement

A subsequence of a string S is a string that can be obtained by deleting zero or more characters from S without changing the order of the remaining characters.
For example, arc, artistic and (an empty string) are all subsequences of artistic; abc and ci are not.

You are given a string A consisting of lowercase English letters.
Find the shortest string among the strings consisting of lowercase English letters that are not subsequences of A.
If there are more than one such string, find the lexicographically smallest one among them.

Constraints

1 \leq |A| \leq 2 \times 10^5

A consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

A

Output

Print the lexicographically smallest string among the shortest strings consisting of lowercase English letters that are not subsequences of A.

Sample Input 1

atcoderregularcontest

Sample Output 1

b

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

Sample Input 2

abcdefghijklmnopqrstuvwxyz

Sample Output 2

aa

Sample Input 3

frqnvhydscshfcgdemurlfrutcpzhopfotpifgepnqjxupnskapziurswqazdwnwbgdhyktfyhqqxpoidfhjdakoxraiedxskywuepzfniuyskxiyjpjlxuqnfgmnjcvtlpnclfkpervxmdbvrbrdn

Sample Output 3

aca



Sample input:
atcoderregularcontest


Sample output:
b

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

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



if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()))

Submission status: Accepted

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

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

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

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


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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/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)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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(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(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))

Submission status: Accepted

Solution code:
from collections import deque
from sys import exit

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(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)))
            exit()
        if prevs[posNext] is None:
            prevs[posNext] = pos
            Q.append((lenAns + 1, posNext))

Submission status: Accepted

Solution code:
import collections
a=raw_input()
trans=[None]*(len(a)+1)
trans[len(a)]=[None]*26
for i, ch in reversed(list(enumerate(a))):
	trans[i]=trans[i+1][:]
	trans[i][ord(ch)-ord('a')]=i+1
q=collections.deque([0])
prev=[None]*(len(a)+1)
prev[0]=-1
try:
	while True:
		cur=q[0]
		q.popleft()
		for i in xrange(26):
			if trans[cur][i]==None:
				result=[chr(ord('a')+i)]
				while cur!=0:
					result.append(a[cur-1])
					cur=prev[cur]
				raise KeyboardInterrupt
			elif prev[trans[cur][i]]==None:
				prev[trans[cur][i]]=cur
				q.append(trans[cur][i])
except KeyboardInterrupt:
	print "".join(reversed(result))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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,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())

Submission status: Accepted

Solution code:

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

Submission status: Accepted

Solution code:
import string

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from __future__ import print_function
from collections import deque
from bisect import bisect_left as bl
input = raw_input
range = xrange

def goto(fr, to):
    i = bl(occ[to], fr+1)
    if i == len(occ[to]): return n+1
    return occ[to][i]

s = [-1]+[ord(c)-97 for c in input()]
n = len(s)-1
occ = [[] for i in range(26)]
for i in range(1, n+1):
    occ[s[i]].append(i)
visit = [None]*(n+2)
visit[0] = (-1, -1) # letter, lastindex
Q = deque()
Q.append(0)

while len(Q):
    p = Q.popleft()
    if p == n+1: break
    for q in range(26):
        qi = goto(p, q)
        if visit[qi]: continue
        visit[qi] = (q, p)
        Q.append(qi)
stack = []
i = n+1
while visit[i][0] != -1:
    stack.append(visit[i][0])
    i = visit[i][1]

for i in reversed(stack):
    print(chr(97+i), end='')