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: Time Limit Exceeded

Solution code:
from bisect import bisect_left

CHARACTERs = 'abcdefghijklmnopqrstuvwxyz'

As = input()
lenA = len(As)

posChars = dict([(ch, []) for ch in CHARACTERs])
for i, A in enumerate(As):
    posChars[A].append(i)
for ch in CHARACTERs:
    posChars[ch].append(lenA)

dp = [0] * lenA + [1, 0]
for i in reversed(range(lenA)):
    dp[i] = min([dp[posChars[ch][bisect_left(posChars[ch], i)] + 1] for ch in CHARACTERs]) + 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: Time Limit Exceeded

Solution code:
from collections import deque
from sys import exit

As = input()

lenA = len(As)
posChars = dict([(ch, lenA) for ch in 'abcdefghijklmnopqrstuvwxyz'])
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 'abcdefghijklmnopqrstuvwxyz':
        posNext = posNexts[pos + 1][ch]
        if posNext == lenA:
            ans = [ch]
            while pos != -1:
                ans.append(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: Time Limit Exceeded

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 = [ord(c) - 97 for c in S()]
    l = len(a)
    r = []
    t = [0] * l
    s = set()
    u = [[] for _ in range(26)]
    k = 1
    sl = 0
    for i in range(l-1,-1,-1):
        c = a[i]
        u[c].append(i)
        t[i] = k
        if c not in s:
            if sl == 25:
                k += 1
                s = set()
                sl = 0
            else:
                sl += 1
                s.add(c)
    t.append(1)
    for i in range(26):
        u[i].reverse()

    def bs(i,c):
        t = u[c]
        if not t or t[-1] <= i:
            return -1
        ma = len(t) - 1
        mi = 0
        mm = (ma+mi) // 2
        while ma > mi:
            mm = (ma+mi) // 2
            if t[mm] > i:
                ma = mm
            else:
                mi = mm + 1
        return t[mm]

    j = -1
    while j < l:
        for c in range(26):
            bi = bs(j,c)
            if bi < 0:
                r.append(c)
                j = l
                break
            if t[bi] < k:
                r.append(c)
                k = t[bi]
                j = bi
                break

    return ''.join([chr(c+97) for c in r])

print(main())

Submission status: Time Limit Exceeded

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 = [ord(c) - 97 for c in S()]
    l = len(a)
    r = []
    t = [0] * l
    s = set()
    u = [[] for _ in range(26)]
    k = 1
    for i in range(l-1,-1,-1):
        c = a[i]
        u[c].append(i)
        s.add(c)
        t[i] = k
        if len(s) == 26:
            k += 1
            s = set()
    t.append(1)
    for i in range(26):
        u[i].reverse()

    def bs(i,c):
        t = u[c]
        if not t or t[-1] <= i:
            return -1
        ma = len(t) - 1
        mi = 0
        mm = (ma+mi) // 2
        while ma > mi:
            mm = (ma+mi) // 2
            if t[mm] > i:
                ma = mm
            else:
                mi = mm + 1
        return t[mm]

    j = -1
    while j < l:
        for c in range(26):
            bi = bs(j,c)
            if bi < 0:
                r.append(c)
                j = l
                break
            if t[bi] < k:
                r.append(c)
                k = t[bi]
                j = bi
                break

    return ''.join([chr(c+97) for c in r])

print(main())

Submission status: Time Limit Exceeded

Solution code:

ord_a = ord('a')

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

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

memo.append((0,f))
result = []

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

  result.append(f.index(0))


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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter
from itertools import product
abc = "abcdefghijklmnopqrstuvwxyz"
A = input()
counter = Counter(A)
EXIT = False

for a in abc:
    if counter[a] == 0:
        print(a)
        EXIT = True
        break
    
# -----------------------------
if not EXIT:
    S = set([A[:2]])
    NS = set()

    for a in A[2:]:
        for s in S:
            NS.update([s, s[0]+a, s[1]+a])
        S, NS = NS, set()

    counter = Counter(S)
    for a, b in product(abc, abc):
        if counter[a+b] == 0:
            print(a+b)
            EXIT = True
            break

# ------------------------------
if not EXIT:    
    S = set([A[:3]])
    NS = set()    

    for a in A[3:]:
        for s in S:
            NS.update([s, s[:1]+a, s[0::2]+a, s[1:3]+a])
        S, NS = NS, set()

    counter = Counter(S)
    for a, b, c in product(abc, abc, abc):
        if counter[a+b+c] == 0:
            print(a+b+c)
            EXIT = True
            break

Submission status: Time Limit Exceeded

Solution code:
import re
import itertools as it

def getInput():
    separator = ' '
    ret_array = []
    while True:
        try:
            row = input().split(sep=separator)
            ret_array.append(row)
        except EOFError:
            break
    return ret_array


def subseq(sub, sup):
    return bool(re.match(sub, sup))


g = getInput()
A = g[0][0]
l = 1
for l in range(1,len(A)):
    # ss = string source
    for ss in it.product(range(97, 123), repeat=l):
        sub = ''.join(map(chr, ss))
        if subseq(sub, A):
            print(sub)

Submission status: Time Limit Exceeded

Solution code:
A=input()
n='abcdefghijklmnopqrstuvwxyz'
def decide(ans):
    place=0
    for i in ans:
        tmp=A[place:].find(i)
        if tmp==-1:
            return False
        place+=tmp+1
    return True
def Next(ans):
    keta=0
    ans=ans[::-1]
    def donext(keta):
        if ans[keta]==26:
            ans[keta]=1
            donext(keta+1)
        else:
            ans[keta]+=1
        return ans
    return donext(keta)[::-1]

i=[0]*10
while True:
    ans=""
    for j in i:
        if j==0:
            continue
        ans+=n[j-1]
    if not decide(ans):
        print(ans)
        break
    i=Next(i)

Submission status: Time Limit Exceeded

Solution code:
from string import ascii_lowercase


def solve(s):
    d = [('', 0)]
    while True:
        e = []
        for ds, di in d:
            max_ci = -1
            for c in ascii_lowercase:
                ci = s.find(c, di) + 1
                ns = ds + c
                if not ci:
                    return ns
                if max_ci >= ci:
                    continue
                max_ci = ci
                e.append((ns, ci))
        d = e


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

Submission status: Time Limit Exceeded

Solution code:
def minsbset(str, n):
    if len(str) < n or n == 0:
        return ""
    return minsbset()
str = input()
n = len(str)
atoz = "abcdefghijklmnopqrstuvwxyz"
ret = ""
subsets1 = set()
subsets1.update(str)
if len(subsets1) < 26:
    for i in range(26):
       if atoz[i] not in subsets1:
           ret = atoz[i]
           break
else:
    subsets2 = set()
    for i1 in range(n):
        for i2 in range(i1+1,n):
            subsets2.add(str[i1] + str[i2])
    if len(subsets2) < 26*26:
        for i1 in range(26):
            for i2 in range(26):
                cand = atoz[i1] + atoz[i2]
                if cand not in subsets2:
                    ret = cand
                    break
            if ret != "":
                break
    else:
        subsets3 = set()
        for i1 in range(n):
            for i2 in range(i1 + 1, n):
                for i3 in range(i2 + 1, n):
                    subsets3.add(str[i1] + str[i2] + str[i3])
        if len(subsets3) < 26 * 26 * 26:
            for i1 in range(26):
                for i2 in range(26):
                    for i3 in range(26):
                        cand = atoz[i1] + atoz[i2] + atoz[i3]
                        if cand not in subsets3:
                            ret = cand
                            break
                    if ret != "":
                        break
                if ret != "":
                    break
        else:
            subsets4 = set()
            for i1 in range(n):
                for i2 in range(i1 + 1, n):
                    for i3 in range(i2 + 1, n):
                        for i4 in range(i3 + 1, n):
                            subsets4.add(str[i1] + str[i2] + str[i3] + str[i4])
            for i1 in range(26):
                for i2 in range(26):
                    for i3 in range(26):
                        for i4 in range(26):
                            cand = atoz[i1] + atoz[i2] + atoz[i3] + atoz[i4]
                            if cand not in subsets4:
                                ret = cand
                                break
                        if ret != "":
                            break
                    if ret != "":
                        break
                if ret != "":
                    break
print(ret)

Submission status: Time Limit Exceeded

Solution code:
from string import ascii_lowercase


def solve(s):
    d = {c: {0: ''} for c in ascii_lowercase}
    while True:
        e = {}
        ans = set()
        for c in ascii_lowercase:
            f = {}
            for dc, dd in d.items():
                for di, ds in dd.items():
                    ci = s.find(c, di) + 1
                    ns = ds + c
                    if not ci:
                        ans.add(ns)
                        continue
                    if ci in f and ns > f[ci]:
                        continue
                    f[ci] = ns
            e[c] = f
        if ans:
            return min(ans)
        d = e


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

Submission status: Time Limit Exceeded

Solution code:
alpha = 'abcdefghijklmnopqrstuvwxyz'

a = input()
flag = False
for i in range(26):
    if (a.find(alpha[i]) == -1):
        print(alpha[i])
        flag = True
        break

if not flag:
    s = 'aa'
    ansflag = False
    while True:
        temp = a
        for i in s:
            index = temp.find(i)
            if index == -1:
                ansflag = True
            else:
                temp = temp[index + 1:]

        if ansflag:
            print(s)
            break

        if s[len(s) - 1] != 'z':
            char = alpha[alpha.find(s[len(s) - 1]) + 1]
            s = s[:len(s) - 1]
            s = s + char
        else:
            length = len(s)
            index = len(s) - 1
            while (index >= 0) & (s[index] == 'z'):
                index -= 1
            
            if index == -1:
                s = ''
                for i in range(length + 1):
                    s = s + 'a'
            else:
                char = alpha[alpha.find(s[index]) + 1]
                s = s[:index]
                s = s + char
                for i in range(length - len(s)):
                    s = s + 'a'

Submission status: Time Limit Exceeded

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():
    s = S()
    l = len(s)

    fm = {}
    def f(i):
        if i in fm:
            return fm[i]
        t = set()
        r = 0
        for j in range(i, l):
            t.add(s[j])
            if len(t) == 26:
                t = set()
                r += 1
        fm[i] = r + 1
        return r + 1

    r = []
    def g(i):
        t = set()
        m = inf
        k = set()
        for j in range(i, l):
            if s[j] not in t:
                ji = f(j+1)
                if m > ji:
                    m = ji
                    k = set([(s[j], j)])
                elif m == ji:
                    k.add((s[j], j))
                t.add(s[j])
                if len(t) == 26:
                    break
        if len(t) < 26:
            for k in string.ascii_lowercase:
                if k not in t:
                    r.append(k)
                    break
        else:
            tr = sorted(list(k))[0]
            r.append(tr[0])
            g(tr[1]+1)

    g(0)

    return ''.join(r)

print(main())

Submission status: Memory Limit Exceeded

Solution code:
from collections import deque
alpha = "abcdefghijklmnopqrstuvwxyz"
A = input()
n = len(A)

links = {}

link = {}
for c in alpha:
    link[c] = n
for i in range(n-1, -1, -1):
    links[i] = dict(link)
    link[A[i]] = i
links[-1] = link

deq = deque()
deq.append(-1)
prev = {-1: (None, "")}
while deq:
    v = deq.popleft()
    if v == n:
        break
    link = links[v]
    for c in alpha:
        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(c)
ans.reverse()
print("".join(ans))

Submission status: Memory Limit Exceeded

Solution code:
from collections import deque
alpha = "abcdefghijklmnopqrstuvwxyz"
A = raw_input()
n = len(A)

links = {}

link = {}
for c in alpha:
    link[c] = n
for i in xrange(n-1, -1, -1):
    links[i] = dict(link)
    link[A[i]] = i
links[-1] = link

deq = deque()
deq.append(-1)
prev = {-1: (None, "")}
while deq:
    v = deq.popleft()
    if v == n:
        break
    link = links[v]
    for c in alpha:
        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(c)
ans.reverse()
print "".join(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *
from bisect import *

A = input()[:-1]
K = [0]*(len(A)) #K[i]: A[i+1:]の部分列に含まれない最小の文字列の長さ
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))

Submission status: Accepted

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

if __name__ == '__main__':
    # sys.setrecursionlimit(1000000)
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:

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