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: Runtime Error

Solution code:
from sys import stdout
# from copy import copy, deepcopy
from functools import lru_cache
from string import ascii_lowercase
from math import inf


def noop(*object): pass
# print = noop # use print() to debug and uncomment this line to mute it

def main():
    ans = solve_case()
    stdout.write("{}\n".format(ans))

def solve_case():
    S = read_str()

    @lru_cache(maxsize=None)
    # the position of the first `char` from `from_idx`
    def next_char_pos(from_idx, char):
        if from_idx == len(S):
            return len(S)
        if S[from_idx] == char:
            return from_idx
        return next_char_pos(from_idx+1, char)

    recon = dict()

    @lru_cache(maxsize=None)
    # the length of the shortest "non subsequence" in S[from_idx:]
    def non_subseq_len(from_idx):
        if from_idx == len(S):
            return 1
        if from_idx > len(S):
            return 0
        ans = inf
        for letter in ascii_lowercase:
            new_ans = non_subseq_len(next_char_pos(from_idx, letter) + 1) + 1
            if ans > new_ans:
                ans = new_ans
                recon[from_idx] = (letter, next_char_pos(from_idx, letter) + 1)
        return ans

    for from_idx in reversed(range(len(S))):
        non_subseq_len(from_idx)

    ans = ''
    idx = 0
    while idx < len(S):
        letter, next_idx = recon[idx]
        ans += letter
        idx = next_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: Runtime Error

Solution code:
import sys
from copy import copy, deepcopy
from functools import lru_cache
from string import ascii_lowercase
from math import inf


def noop(*object): pass
# print = noop # use print() to debug and uncomment this line to mute it

def main():
    ans = solve_case()
    sys.stdout.write("{}\n".format(ans))

def solve_case():
    S = read_str()

    @lru_cache(maxsize=None)
    # the position of the first `char` from `from_idx`
    def next_char_pos(from_idx, char):
        if from_idx == len(S):
            return len(S)
        if S[from_idx] == char:
            return from_idx
        return next_char_pos(from_idx+1, char)

    recon = dict()

    @lru_cache(maxsize=None)
    # the length of the shortest "non subsequence" in S[from_idx:]
    def non_subseq_len(from_idx):
        if from_idx == len(S):
            return 1
        if from_idx > len(S):
            return 0
        ans = inf
        for letter in ascii_lowercase:
            new_ans = non_subseq_len(next_char_pos(from_idx, letter) + 1) + 1
            if ans > new_ans:
                ans = new_ans
                recon[from_idx] = (letter, next_char_pos(from_idx, letter) + 1)
        return ans

    for from_idx in reversed(range(len(S))):
        non_subseq_len(from_idx)

    ans = ''
    idx = 0
    while idx < len(S):
        letter, next_idx = recon[idx]
        ans += letter
        idx = next_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: Runtime Error

Solution code:
import sys
from copy import copy, deepcopy
from functools import lru_cache
from string import ascii_lowercase
from math import inf


def noop(*object): pass
# print = noop # use print() to debug and uncomment this line to mute it

def main():
    ans = solve_case()
    sys.stdout.write("{}\n".format(ans))

def solve_case():
    S = read_str()

    @lru_cache(maxsize=None)
    # the position of the first `char` from `from_idx`
    def next_char_pos(from_idx, char):
        if from_idx == len(S):
            return len(S)
        if S[from_idx] == char:
            return from_idx
        return next_char_pos(from_idx+1, char)

    recon = dict()

    @lru_cache(maxsize=None)
    # the length of the shortest "non subsequence" in S[from_idx:]
    def non_subseq_len(from_idx):
        if from_idx == len(S):
            return 1
        if from_idx > len(S):
            return 0
        ans = inf
        for letter in ascii_lowercase:
            new_ans = non_subseq_len(next_char_pos(from_idx, letter) + 1) + 1
            if ans > new_ans:
                ans = new_ans
                recon[from_idx] = (letter, next_char_pos(from_idx, letter) + 1)
        return ans

    for from_idx in reversed(range(len(S))):
        non_subseq_len(from_idx)

    ans = ''
    idx = 0
    while idx < len(S):
        letter, next_idx = recon[idx]
        ans += letter
        idx = next_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: Runtime Error

Solution code:
a = input() + "$"
n = len(a)

alph = "abcdefghijklmnopqrstuvwxyz"
dp = [0] * (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
# print(next_)

def solve(i):
    if dp[i] != 0:
        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: Runtime Error

Solution code:
# numpyとか使って高速化お遊び
import sys
import numpy as np

def main():
    inf = 10 ** 7
    s = sys.stdin.readline()[:-1]
    n = len(s)
    s += "".join(chr(i + 97) for i in range(26))
    # print(s)
    # 次をその文字にした時の「長さ、位置」
    size = np.zeros(26, "i8")
    pos = [n + i for i in range(26)]
    # 解答復元のための移動先
    nxt = [-1] * n
    # 後ろの文字から順に見る
    for i in range(n - 1, -1, -1):
        # 次をどの文字にすれば短くなるか調べる
        # 同じ長さの時は辞書順優先
        # codeはaを0として番号化したもの
        min_size_code = size.argmin()[0]
        now_code = ord(s[i]) - 97
        size[now_code] = size[min_size_code] + 1
        pos[now_code] = i
        nxt[i] = pos[min_size_code]
        # print(size)
        # print(pos)
        # print(nxt)
        # print()
    # 最短になる最初の文字を調べて、nxtの順にたどる
    min_size_code = size.argmin()[0]
    i = pos[min_size_code]
    ans = s[i]
    while i < n:
        i = nxt[i]
        ans += s[i]
    print(ans)

main()

Submission status: Runtime Error

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]
        memo[i][alpha2[s[i]]]=i+1

    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: Runtime Error

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]
        memo[i][alpha2[s[i]]]=i+1
    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: Runtime Error

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]
            memo[i][alpha2[s[i]]]=i+1
    
    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: Runtime Error

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]
        memo[i][alpha2[s[i]]]=i+1
    
    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: Runtime Error

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]
        memo[i][alpha2[s[i]]]=i+1
    
    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: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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+"\n")
        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: Runtime Error

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

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: Runtime Error

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)

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: Runtime Error

Solution code:
A=str(input())
memo=[]
count=0
ans=""
index=[]
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):
        count=0
        memo=[]
        index.append(len(A)-1-i)
for i in "abcdefghijklmnopqrstuvwxyz":
    if(i not in memo):
        ans+=i
        break
num=0
index=index[::-1]

a=0
b=0
for j in range(0,len(index)-1):
    a=index[j]
    b=index[j+1]
    print(a,b)
    target=A[a:b]
    num=target.find(ans[j])
    for i in "abcdefghijklmnopqrstuvwxyz":
        if(i not in target[num:]):
            ans+=i
            break

target=A[index[len(index)-1]:]
num=target.find(ans[len(index)-1])
for i in "abcdefghijklmnopqrstuvwxyz":
    if(i not in target[num:]):
        ans+=i
        break
ans+="\n"
print(ans)

Submission status: Runtime Error

Solution code:
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
//bc|abbbc|baca|aacb->最短は絶対4つ、最初の区間にない英単語を選ぶ、次の区間では一個前の区間で選んだ英単語の後ろにない最小の英単語を選ぶ
//aaba
int b[200005]; // ある区間でi以降(i含め)で出てきた文字の集合
int c[200005]; // ある区間でi以降の最小の文字
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin>>s;
  for(int i=s.length()-1;i>=0;i--){
    b[i]=b[i+1]|(1<<(s[i]-'a'));
    c[i]=c[i+1];
    while(b[i]&(1<<c[i]))c[i]++;
    if(c[i]==26){
      b[i]=c[i]=0;
    }
  }
  for(int i=0;i<s.length();++i){
    char x=c[i]+'a';
    cout<<x;
    while(i<s.length()&&x!=s[i])i++;
  }
  cout<<endl;
  return 0;
}

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from math import *
import random

def readln():
    return list(map(int,(input().split(" "))))

def get(p,c):
    if c == 0: return ""

    for i in range(M):
        if F[p][i] == -1: return chr(i + ord('a'))

        if C[F[p][i]] < C[p] :
            return chr(i + ord('a')) + get(F[p][i],c-1)

A = "a" + input()
N,M = len(A),26
C = [0 for i in range(N)]
F = [[-1 for j in range(M)] for i in range(N)]

start = N - 1

for i in range(N):
    idx = N - i - 1
    k = ord(A[idx]) - ord('a')

    if(idx < N - 1):
        for j in range(M):
            F[idx][j] = F[idx+1][j]
        F[idx][ord(A[idx + 1]) - ord('a')] = idx + 1
    C[idx] = N
    for j in range(M):
        if F[idx][j] >= 0 :
            value = C[F[idx][j]]
        else:
            value = 0
        if C[idx] > value + 1:
            C[idx] = value + 1
ans = get(0,C[0])
print(ans)