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

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

if __name__ =='__main__':
    main()

Solution (Python):

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

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

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

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

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

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

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

Solution (Python):


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

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

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

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

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

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

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

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

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

Solution (Python):

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

Solution (Python):
import string

if __name__ == '__main__':
    A = input()

    p = {}
    for x in string.ascii_lowercase:
        p[x] = len(A)
    
    '''
    tb
    1つ目：
    2つ目：アルファベット
    3つ目：
    '''
    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))

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

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

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

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