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: Wrong Answer

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)
if prv!=0:
    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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
S = list(map(lambda x: ord(x) - ord("a"), list(input()[: -1])))
S.reverse()
N = len(S)
dp = [[N] * 26 for _ in range(N + 1)]
dpgo = [[-1] * 26 for _ in range(N + 1)]
for j in range(26): dp[0][j] = 1
for i in range(N):
  for j in range(26):
    if j == S[i]: continue
    dp[i + 1][j] = dp[i][j]
    dpgo[i + 1][j] = dpgo[i][j]
  for j in range(26):
    if dp[i + 1][S[i]] > dp[i][j] + 1:
      dp[i + 1][S[i]] = dp[i][j] + 1
      dpgo[i + 1][S[i]] = j
  #print(S[i], dp[i + 1], dpgo[i])
res = []
x = min(dp[-1])
y = 0
for j in range(26):
  if dp[-1][j] == x:
    y = j
    break
for i in range(N, -1, -1):
  if dp[i][y] == x:
    res.append(chr(y + ord("a")))
    x -= 1
    y = dpgo[i][y]
  #print(dpgo[i])
res.reverse()
print("".join(res))

Submission status: Wrong Answer

Solution code:
a=input()
yn=0
for i in range(1,5):
    for j in range(26**i):
        num=j
        str=""
        for k in range(i):
            str=chr(97+(num%26))+str
            num=num//26
        if str not in a:
            yn=1
            print(str)
            break
    if yn==1:
        break

Submission status: Wrong Answer

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)

#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 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: Wrong Answer

Solution code:
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] = i if c == j else na[i + 1][j]

dp = [INF] * (N + 1)
dp[N] = 0
recon = [None] * N
for i in range(N - 1, -1, -1):
    for j in range(26):
        ni = na[i + 1][j]
        if dp[i] > dp[ni] + 1:
            dp[i] = dp[ni] + 1
            recon[i] = (chr(a + j), ni)


# for j in range(26):
i = 0
ans = []
while i < N:
    c, ni = recon[i]
    ans.append(c)
    i = ni

print(''.join(ans))

Submission status: Wrong Answer

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

for i in range(L-1):
    for moji in alphabetlist:
        if dic[moji]:
            index=bisect.bisect_left(dic[moji],pos)
            npos=dic[moji][index]
            if dp[npos+1]<L-(i+1):
                pos=npos+1
                ans.append(moji)
                break

if pos==N-1:
    ans.append("a")
    print("".join(ans))
else:
    s=set([])
    for i in range(pos+1,N):
        s.add(A[i])
    for moji in alphabetlist:
        if moji not in s:
            ans.append(moji)
            break
    print("".join(ans))

Submission status: Wrong Answer

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

for i in range(L-1):
    for moji in alphabetlist:
        if dic[moji]:
            index=bisect.bisect_left(dic[moji],pos)
            npos=dic[moji][index]
            if dp[npos+1]<L-(i+1):
                pos=npos
                ans.append(moji)
                break

if pos==N-1:
    ans.append("a")
    print("".join(ans))
else:
    s=set([])
    for i in range(pos+1,N):
        s.add(A[i])
    for moji in alphabetlist:
        if moji not in s:
            ans.append(moji)
            break
    print("".join(ans))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
S = list(input())[: -1]
N = len(S)
dp = [[[N, 0] for _ in range(26)] for _ in range(N + 1)]
a = ord("a")
S.reverse()
cs = [[0] * 26 for _ in range(N + 1)]
for i in range(N):
  for j in range(26): cs[i + 1][j] += cs[i][j]
  cs[i + 1][ord(S[i]) - a] += 1
for j in range(26):
  dp[0][j][0] = 1

for i in range(N):
  x = ord(S[i]) - a
  for j in range(26):
    if x == j: continue
    if dp[i + 1][j][0] > dp[i][j][0]:
      dp[i + 1][j][0] = dp[i][j][0]
      dp[i + 1][j][1] = dp[i][j][1]
  for j in range(26):
    if dp[i + 1][x][0] > dp[i][j][0]:
      if cs[i][j] - cs[dp[i][j][1] + 1][j]: continue
      dp[i + 1][x][0] = dp[i][j][0] + 1
      dp[i + 1][x][1] = i

x = 0
res = []
for j in range(26):
  if dp[-1][x][0] > dp[-1][j][0]: x = j
#print(dp)
ln = dp[-1][x][0]
i = N
while len(res) < ln:
  #print(i, res)
  res.append(chr(x + a))
  i = dp[i][x][1] - (i == dp[i][x][1])
  for j in range(26):
    if dp[i][x][0] > dp[i][j][0]: x = j
print("".join(res))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
S = list(input())[: -1]
N = len(S)
dp = [[[N, 0] for _ in range(26)] for _ in range(N + 1)]
a = ord("a")
S.reverse()
cs = [[0] * 26 for _ in range(N + 1)]
for i in range(N):
  for j in range(26): cs[i + 1][j] += cs[i][j]
  cs[i + 1][ord(S[i]) - a] += 1
for j in range(26):
  dp[0][j][0] = 1

for i in range(N):
  x = ord(S[i]) - a
  for j in range(26):
    if x == j: continue
    if dp[i + 1][j][0] > dp[i][j][0]:
      dp[i + 1][j][0] = dp[i][j][0]
      dp[i + 1][j][1] = dp[i][j][1]
  for j in range(26):
    if dp[i + 1][x][0] > dp[i][j][0]:
      if cs[i][j] - cs[dp[i][j][1] + 1][j]: continue
      dp[i + 1][x][0] = dp[i][j][0] + 1
      dp[i + 1][x][1] = i

x = 0
res = []
for j in range(26):
  if dp[-1][x][0] > dp[-1][j][0]: x = j
#print(dp)
i = N
while i:
  #print(i, res)
  res.append(chr(x + a))
  i = dp[i][x][1] - (i == dp[i][x][1])
  for j in range(26):
    if dp[i][x][0] > dp[i][j][0]: x = j
print("".join(res))

Submission status: Wrong Answer

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][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][i] == dp[npnt][i]:
      ans.append(i)
      break
  else:
    ans.append(0)
    flg = 1
  pnt = npnt

Submission status: Wrong Answer

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]
while True:
  c = ans[-1]
  pnt = n-dp[pnt][c]
  prtp = bisect.bisect_right(prt,pnt)
  if prtp == len(prt):
    for i in range(26):
      pnt += 1
      if dp[pnt][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][i] == dp[npnt][i]:
      ans.append(i)
      break
  else:
    ans.append(0)
  pnt = npnt

Submission status: Wrong Answer

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]
while True:
  c = ans[-1]
  pnt = n-dp[pnt][c]
  prtp = bisect.bisect_right(prt,pnt)
  if prtp == len(prt):
    for i in range(26):
      if dp[pnt][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][i] == dp[npnt][i]:
      ans.append(i)
      break
  else:
    ans.append(0)
  pnt = npnt

Submission status: Wrong Answer

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]] != dp[0]:
    ans.append(i)
    break
else:
  ans.append(0)
pnt = prt[0]
while True:
  c = ans[-1]
  pnt = n-dp[pnt][c]
  prtp = bisect.bisect_right(prt,pnt)
  if prtp == len(prt):
    for i in range(26):
      if dp[pnt][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][i] == dp[npnt][i]:
      ans.append(i)
      break
  else:
    ans.append(0)
  pnt = npnt

Submission status: Wrong Answer

Solution code:
import string
char=string.ascii_lowercase
numbering={}
for i in range(26):
    numbering[char[i]]=i
A=input()
n=len(A)
next=[[n]*26 for i in range(n+1)]
for i in range(n-1,-1,-1):
    for j in range(26):
        next[i][j]=next[i+1][j]
    next[i][numbering[A[i]]]=i

dp=["z"*n for i in range(n+1)]
dp[n]="a"
for i in range(n-1,-1,-1):
    m=0
    length=n
    for c in range(26):
        if next[i][c]==n and char[c]<dp[i]:
            dp[i]=char[c]
            break
        else:
            if length>len(dp[next[i][c]+1])+1:
                length=len(dp[next[i][c]+1])+1
                m=c
    try:
        if char[m]+dp[next[i][m]+1]<dp[i]:
            dp[i]=char[m]+dp[next[i][m]+1]
    except IndexError:
        pass
print(dp[0])

Submission status: Wrong Answer

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(i):
    if dp[i] != -1:
        return dp[i]
    tmp = n + 1
    for char in range(26):
        if next_[char][i] == -1:
            dp[i] = 1
            return dp[i]
        tmp = min(solve(next_[char][i]) + 1 , tmp)
    dp[i] = tmp
    return dp[i]

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

print("".join(ans))

Submission status: Wrong Answer

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 = 0
for _ in range(L+1):
    best = Best[max(dp[ind])]
    for k in range(26):
        if Best[dp[ind][k]] == best:
            ans += alp[k]
            if ind != N:
                ind = dp[ind+1][k]
            break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
inf = 10**10
A = input()
N = len(A)
abc = 'abcdefghijklmbopqrstuvwxyz'
s_to_i = [defaultdict(lambda:N) for _ in range(N+1)]
for x in abc:   
    s_to_i[-1][x] = N
for i in range(N)[::-1]:
    for x in abc:
        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].values())+1
    dp[i] = dp[now]+1
n = dp[0]
now = 0
ans = []
for i in range(n):
    for x in abc:
        tmp = s_to_i[now][x]+1
        if dp[tmp] <= n-i-1:
            ans.append(x)
            now = tmp
            break
print(*ans, sep = '')

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    a = input()
    n = len(a)
    f = defaultdict(lambda : [])
    for i in range(n):
        f[a[i]].append(i)
    alp = list("abcdefghijklmnopqrstuvwxyz")
    l = [i for i in alp]
    for i in range(3):
        l += [i+j for i in l for j in alp]
    for s in l:
        x = -1
        for i in s:
            j = bisect.bisect_right(f[i],x)
            if j >= len(f[i]):
                print(s)
                return
            x = f[i][j]
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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():
            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: Wrong Answer

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.appendleft(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: Wrong Answer

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:
            print(k)
            ans.append(97+c)
            cnt = k
            break
        

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

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] = np.zeros((2,26), dtype=np.int32)
dp[N][0,:] = INF
dp[N][1,:] = 0

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

answer = []
i = 0
while i < N:
    # 辞書順で、作れる長さが一番短い文字
    x = np.argmin(dp[i][1])
    answer.append(chr(ord('a') + x))
    # その文字の場所に移動
    i = dp[i][0,x]
    i += 1

print(''.join(answer))

Submission status: Wrong Answer

Solution code:
import bisect

S=list(input())
L=[[]for i in range(26)]
A=["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"]

for i in range(len(S)):
    for j in range(26):
        if S[i]==A[j]:
            L[j].append(i)
for i in range(26):
    L[i].append(10**10)
#print(L)


B=[""]+A
for a in range(27):
    for b in range(27):
        
        for c in range(27):
            
            for d in range(1,27):
                num=[]
                if a!=0:
                    num.append(a-1)
                if b!=0:
                    num.append(b-1)
                if c!=0:
                    num.append(c-1)
                num.append(d-1)
                cnt=0
                for e in range(len(num)):
                    #print(num[e],cnt)
                    cnt=L[num[e]][bisect.bisect_left(L[num[e]],cnt)]+1
                    if cnt>10**6:
                        ANS=""
                        #print(cnt)
                        for f in range(len(num)):
                            ANS+=A[num[f]]
                        print(ANS)
                        exit()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
s = input()
def num(letter):
	return ord(letter) - 97
def let(number):
	return chr(number + 97)
#alph = set([let(i) for i in range(26)])

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
				continue
		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: Wrong Answer

Solution code:
from collections import Counter
s = input()
def num(letter):
	return ord(letter) - 97
def let(number):
	return chr(number + 97)
#alph = set([let(i) for i in range(26)])

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 < ok:
			if i == d[cnt]:
				for j in range(26):
					if used[j] == False:
						ans += let(j)
						break
				used = [False] * 26
				cnt += 1
				skip = True
				continue
		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: Wrong Answer

Solution code:
from collections import Counter
s = input()
def num(letter):
	return ord(letter) - 97
def let(number):
	return chr(number + 97)
#alph = set([let(i) for i in range(26)])

ok = 0
ng = len(s)
while ng-ok > 1:
	mi = (ok+ng) // 2
	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
	if cnt >= mi:
		ok = mi
	else:
		ng = mi
#print(ng)
if ng == 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
	for i in range(len(s)):
		if cnt < ok:
			if i == d[cnt]:
				for j in range(26):
					if used[j] == False:
						ans += let(j)
						break
				used = [False] * 26
				cnt += 1
				skip = True
				continue
		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: Wrong Answer

Solution code:
from collections import Counter
s = input()
def num(letter):
	return ord(letter) - 97
def let(number):
	return chr(number + 97)
#alph = set([let(i) for i in range(26)])

ok = 0
ng = len(s)
while ng-ok > 1:
	mi = (ok+ng) // 2
	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
	if cnt >= mi:
		ok = mi
	else:
		ng = mi
#print(ng)
if ng == 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
	for i in range(d[-1] + 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
			continue
		if skip:
			if s[i] == ans[-1]:
				skip = False
			continue

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

	print(ans + "a")

Submission status: Wrong Answer

Solution code:
A=str(input())
memo=[]
count=0
ans=[]
for i in range(0,len(A)):
    target=A[len(A)-1-i]
    if(target not in memo):
        memo.append(target)
        count+=1
    if(count==26):
        ans.append(target)
        count=0
        memo=[]
for i in "abcdefghijklmnopqrstuvwxyz":
    if(i not in memo):
        ans.append(i)
        break
result=""
for j in range(0,len(ans)):
    result+=ans[len(ans)-1-j]
result+="\n"
print(result)

Submission status: Wrong Answer

Solution code:
A=str(input())
memo=[]
count=0
ans=[]
for i in range(0,len(A)):
    target=A[len(A)-1-i]
    if(target not in memo):
        memo.append(target)
        count+=1
    if(count==26):
        ans.append(target)
        count=0
        memo=[]
for i in "abcdefghijklmnopqrstuvwxyz":
    if(i not in memo):
        ans.append(i)
        break
result=""
for j in range(0,len(ans)):
    result+=ans[len(ans)-1-j]

print(result)

Submission status: Wrong Answer

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:
        r += chr(orda + rt[i])
        i = next_i[i][rt[i]] + 1


    print(r)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import product
A = input()
d = defaultdict(lambda: False)
f3 = f2 = f1 = "."
for a in A:
    d[a] = d[f1+a] = d[f2+f1+a] = d[f3+f2+f1+a] = True
    f3, f2, f1 = f2, f1, a
abc = list(map(chr, range(97, 97+26)))
ABC = []
for i in range(1, 5):
    ABC.extend(product(abc, repeat=i))
for c in ABC:
    c = "".join(c)
    if not d[c]:
        print(c)
        break