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:
a = input()

abc = set('abcdefghijklmnopqrstuvwxyz')
d = {}

for i in 'abcdefghijklmnopqrstuvwxyz':
    d[i] = 0

dp = []

for s in a[::-1]:
    d[s] = min(d.values())+1
    dp.append(d[s])

start = min(d.values())+1

dp.reverse()
cur = start
ans = str()
id = int()
prev = int()

def find(dp, i):
    for j, n in enumerate(dp):
        if n != i:
            return j

for i in range(cur, 1, -1):
    id = dp.index(i-1)
    b = a[id:find(dp[id:], i-1)]
    c = a[prev:id]
    n = list(set(b)-set(c))
    d = sorted(n)[0] if len(n) != 0 else 'a'
    ans += d
    prev = a[id:].find(d) + id

c = a[prev:]
n = list(abc-set(c))
ans += sorted(n)[0] if len(n) != 0 else 'a'

print(ans)

Submission status: Wrong Answer

Solution code:
a = input()

abc = set('abcdefghijklmnopqrstuvwxyzabc')
d = {}

for i in 'abcdefghijklmnopqrstuvwxyz':
    d[i] = 0

dp = []

for s in a[::-1]:
    d[s] = min(d.values())+1
    dp.append(d[s])

dp.append(min(d.values())+1)

dp.reverse()
cur = dp[0]
ans = str()
id = int()
if dp[0] != dp[1]:
    ans += 'a'
    cur -= 1
    id = a.index('a')

for i in range(cur, 1, -1):
    id = dp.index(i-1)
    ans += a[id]

aset = set(a[id+1:])
ans += sorted(list(aset^abc))[0]

print(ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    a = S()
    l = len(a)
    t = {}
    for c in string.ascii_lowercase:
        t[c] = l
    b = [(0,0,0) for _ in range(l)]
    b.append((1,0,0))
    b.append((0,0,0))

    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 and len(r) < 10:
        r += b[i][1]
        i = b[i][2]
    return r

print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    a = S()
    l = len(a)
    t = {}
    for c in string.ascii_lowercase:
        t[c] = l
    b = [(1,0,0) for _ in range(l)]
    b.append((1,'a',l))
    b.append((0,'',l+1))

    for c,i in reversed(list(zip(a,range(l)))):
        t[c] = i
        b[i] = min([(b[t[d]+1][0] + 1,d,t[d]+1) for d in string.ascii_lowercase])

    r = ''
    i = 0
    while i < l and len(r) < 10:
        r += b[i][1]
        i = b[i][2]
    return r

print(main())

Submission status: Wrong Answer

Solution code:
import string

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

    p = {}
    for x in string.ascii_lowercase:
        p[x] = len(A)
    # print(p)
    '''
    tb
    1つ目：
    2つ目：アルファベット
    3つ目：
    '''
    tb = [(0, 0, 0)] * len(A)
    tb.append((1, 0, 0))
    tb.append((0, 0, 0))
    # print(tb)
    for i, x in reversed(list(enumerate(A))):
        p[x] = i
        tb[i] = min([(tb[p[c] + 1][0] + 1, c, p[c] + 1) for c in string.ascii_lowercase])
        print(tb)
    i = 0
    ans = []
    while i < len(A):
        ans.append(tb[i][1])
        i = tb[i][2]

    print("".join(ans))

Submission status: Wrong Answer

Solution code:
A=str(input())
N=len(A)

number=[0]*26
kazu=0
for i in range(N-1,-1,-1):
  if kazu==25 and number[ord(A[i])-97]==0:
    print(A[i])
  elif number[ord(A[i])-97]==0:
    number[ord(A[i])-97]+=1 
    kazu+=1
print(number)

Submission status: Wrong Answer

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:
                    break
                max_ci = ci
                e.append((ns, ci))
        d = e


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

Submission status: Wrong Answer

Solution code:
from string import ascii_lowercase


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


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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
alpha = "abcdefghijklmnopqrstuvwxyz"
A = raw_input()
n = len(A)
P = len(alpha)
B = ord('a')

links1 = [None]*n
links2 = [None]*n

link = {}
for i in xrange(n-1, -1, -1):
    links1[i] = dict(link)
    link[A[i]] = i
    links2[i] = dict(link)

memo = {}
def dfs(i, mode):
    if (i, mode) in memo:
        return memo[i, mode]
    link = links1[i] if mode else links2[i]
    result = None
    for c in alpha:
        if c not in link:
            result = [1, ord(c)-B]
            break
    if result is None:
        for c in alpha:
            if link[c] == i:
                res = dfs(i, 1)[:]
                res[0] += 1
                res[1] = res[1]*P + ord(c) - B
            else:
                res = dfs(link[c], 0)[:]
                res[0] += 1
                res[1] = res[1]*P + ord(c) - B
            if result is None or res < result:
                result = res
    memo[i, mode] = result
    return result
cnt, codes = dfs(0, 0)
ans = []
for i in xrange(cnt):
    ans.append(chr((codes%P)+B))
    codes /= P
print "".join(ans)

Submission status: Wrong Answer

Solution code:
alpha = "abcdefghijklmnopqrstuvwxyz"
A = raw_input()
n = len(A)

links1 = [None]*n
links2 = [None]*n

link = {}
for i in xrange(n-1, -1, -1):
    links1[i] = dict(link)
    link[A[i]] = i
    links2[i] = dict(link)

memo = {}
def dfs(i, mode):
    if (i, mode) in memo:
        return memo[i, mode]
    link = links1[i] if mode else links2[i]
    result = None
    for c in alpha:
        if c not in link:
            result = c
            break
    if result is None:
        for c in alpha:
            if link[c] == i:
                res = c + dfs(i, 1)
            else:
                res = c + dfs(link[c], 0)
            if result is None or len(res) < len(result) or res < result:
                result = res
    memo[i, mode] = result
    return result
print dfs(0, 0)

Submission status: Time Limit Exceeded

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


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

Solution code:
def main():
    # import sys
    # readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    from collections import deque

    A = input()
    N = len(A)
    a = ord('a')

    INF = N
    na = [[INF] * 26 for _ in range(N)]
    for i in range(N - 1, -1, -1):
        c = ord(A[i]) - ord('a')
        for j in range(26):
            na[i][j] = i if c == j else na[(i + 1) % N][j]

    q = deque()
    q.append(([], -1))

    while q:
        s, i = q.popleft()
        for j in range(26):
            ni = na[i + 1][j]
            ns = s + [chr(a + j)]
            if ni == INF:
                print(''.join(ns))
                exit()
            else:
                q.append((ns, ni))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


A = input()
N = len(A)
a = ord('a')

INF = N
na = [[INF] * 26 for _ in range(N)]
for i in range(N - 1, -1, -1):
    c = ord(A[i]) - ord('a')
    for j in range(26):
        na[i][j] = i if c == j else na[(i + 1) % N][j]

q = deque()
q.append(('', -1))

while q:
    s, i = q.popleft()
    for j in range(26):
        ni = na[i + 1][j]
        if ni == INF:
            print(s + chr(a + j))
            exit()
        else:
            q.append((s + chr(a + j), ni))

Submission status: Time Limit Exceeded

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

Solution code:
import sys
from copy import copy, deepcopy
from functools import lru_cache
from string import ascii_lowercase
# from math import inf
inf = float('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: Time Limit Exceeded

Solution code:
import string
import numpy as np
char=string.ascii_lowercase
numbering={}
for i in range(26):
    numbering[char[i]]=i
A=input()
n=len(A)
next=np.zeros((n+1)*26,dtype=int)
next=next.reshape((n+1,26))
next[n]+=n+1
next[n][numbering[A[n-1]]]=n
for i in range(n-1,-1,-1):
    next[i]=next[i+1]
    next[i][numbering[A[i]]]=i

dp=np.array(["あ" for i in range(n+3)],dtype=object)
if A[n-1]!="a":
    dp[n]="a"
else:
    dp[n]="b"
dp[n+1]="a"
dp[n+2]="z"*n
for i in range(n-1,-1,-1):
    index=np.argmax(next[i])
    if next[i][index]>n:
        dp[i]=char[index]
        continue
    else:
        index2=np.argmin(list(map(len,dp[next[i]+1])))
        dp[i]=char[index2]+dp[next[i][index2]+1]
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
import string
import numpy as np
char=string.ascii_lowercase
numbering={}
for i in range(26):
    numbering[char[i]]=i
A=input()
n=len(A)
next=np.zeros((n+1)*26,dtype=int)
next=next.reshape((n+1,26))
next[n]+=n+1
next[n][numbering[A[n-1]]]=n
for i in range(n-1,-1,-1):
    next[i]=next[i+1]
    next[i][numbering[A[i]]]=i

dp=["あ" for i in range(n+3)]
if A[n-1]!="a":
    dp[n]="a"
else:
    dp[n]="b"
dp[n+1]="a"
dp[n+1]="z"*n
for i in range(n-1,-1,-1):
    index=np.argmax(next[i])
    if next[i][index]>n:
        dp[i]=char[index]
        continue
    else:
        lis=[dp[next[i][c]+1] for c in range(26)]
        lis=np.array(list(map(len,lis)))
        index2=np.argmin(lis)
        dp[i]=char[index2]+dp[next[i][index2]+1]
print(dp[0])

Submission status: Time Limit Exceeded

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+1]*26 for i in range(n+1)]
next[n][numbering[A[n-1]]]=n
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 dp[i]>char[m]+dp[next[i][m]+1] and len(dp[i])>len(dp[next[i][m]+1])+1:
            dp[i]=char[m]+dp[next[i][m]+1]
    except IndexError:
        pass
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
INF = N+1
nex = [[INF]*26 for _ in range(N+1)]
for i,c in enumerate(S[::-1]):
    ic = ord(c) - ord('a')
    for j in range(26):
        nex[N-i-1][j] = N-i-1 if j==ic else nex[N-i][j]

dp = [N] * (N+3)
dp[INF] = dp[INF+1] = 0
for i in range(N,-1,-1):
    tmp = INF
    for j in range(26):
        tmp = min(tmp, dp[nex[i][j]+1]+1)
        if tmp == 1: break
    dp[i] = tmp

ans = []
i = 0
for v in range(dp[0]-1,-1,-1):
    for j in range(26):
        if dp[nex[i][j]+1] != v: continue
        ans.append(chr(j + ord('a')))
        i = nex[i][j]+1
        break

print(''.join(ans))

Submission status: Time Limit Exceeded

Solution code:
a = list(map(lambda x: ord(x)-ord("a"), list(input())))
n = len(a)
m = 26

b = [None]*(n+m)
prev = [0]*m
for i in range(m):
    b[n+i] = (1, (i,))
    prev[i] = n+i

for i in reversed(range(n)):
    ai = a[i]
    tmp = min(b[j] for j in prev)
    b[i] = (tmp[0]+1, (ai,)+tmp[1])
    prev[ai] = i
tmp = min(b[j] for j in prev)
ans = "".join(chr(ord("a")+i) for i in tmp[1])
print(ans)

Submission status: Time Limit Exceeded

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

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

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

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
def C(x, i):
    now = i
    for i in range(x):
        now = max(s_to_i[now].values())+1
        if now == N+1:
            return True
    return False
def bisect(i):
    ok = N+1
    ng = 0
    while ok-ng>1:
        mid = (ok+ng)//2
        if C(mid, i):
            ok = mid
        else:
            ng = mid
    return ok
dp = [bisect(i) for i in range(N+1)]
n = dp[0]
ans = []
now = 0
for i in range(n):
    for x in abc:
        tmp = now
        tmp = s_to_i[now][x]+1
        if tmp>N or dp[tmp] == n-i-1:
            ans.append(x)
            now = tmp
            break

print(*ans, sep = "")

Submission status: Time Limit Exceeded

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()
        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()
    i = pos[min_size_code]
    ans = s[i]
    while i < n:
        i = nxt[i]
        ans += s[i]
    print(ans)

main()

Submission status: Time Limit Exceeded

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

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    s=input()
    alpha="abcdefghijklmnopqrstuvwxyz"
    #s=alpha*8000
    #s="a"*200000
    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: Time Limit Exceeded

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    sys.setrecursionlimit(100000)
    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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

S = input()
N = len(S)

# nxt[i][c] := i文字目以降で最初に文字cが登場するindex(存在しないときはN)
nxt = list2d(N+1, 26, N)
for i in range(N-1, -1, -1):
    for c in range(26):
        nxt[i][c] = nxt[i+1][c]
    c = ord(S[i]) - 97
    nxt[i][c] = i

# dp[i] := i文字目以降について「部分文字列とならない」最短の文字列長
dp = [INF] * (N+1)
# rest[i][(c, j)] := 位置iから見て、最小達成に用いた文字cと、次に使う文字のindexj
rest = [None] * (N+1)
dp[N] = 1
# 常に自分より後ろでの最小が必要になるので、後ろから埋めていく
for i in range(N-1, -1, -1):
    # iから見て先頭として使う文字を26通り全部試す
    # abcを昇順で回して、最小更新条件を等号なしにすることで、辞書順で小さい方を優先できる
    for c in range(26):
        # 次の文字がない時
        if nxt[i][c] == N:
            if dp[i] > 1:
                dp[i] = 1
                rest[i] = (c, N)
        # 次の文字がある時
        else:
            # i以降に文字cが出現するindex+1の位置での最短文字列長 + 1
            # 例えばaについてなら、a****となるので、****での最小とaの分で+1
            if dp[i] > dp[nxt[i][c]+1] + 1:
                dp[i] = dp[nxt[i][c]+1] + 1
                rest[i] = (c, nxt[i][c]+1)

# 復元
i = 0
ans = []
while i < N:
    c, idx = rest[i]
    ans.append(chr(c+97))
    i = idx
print(''.join(ans))

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
N = len(S)
def c2i(c):
  return ord("c") - ord("a")
def i2c(i):
  return chr(i + ord("a"))
dp = [[i2c(i)] for i in range(26)]
class SegTree:
  def segfunc(self, x, y):
    if x == ["0"]: return y
    if y == ["0"]: return x
    if len(x) == len(y):
      if x > y: return y
      return x
    else:
      if len(x) > len(y): return y
      return x
  def __init__(self, n, ide_ele, init_val):
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]  
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res
seg = SegTree(26, ["0"], dp)
for i in range(N):
  for j in range(26):
    if S[i] == i2c(j):
      p = seg.query(0, 26)
      seg.update(j, p + [i2c(j)])
print("".join(seg.query(0, 26)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import copy

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

INF = 10 ** 9
N = len(S)
dp = [None] * (N+1)
# そこから始めたとき、次にxが現れる位置、および、次にxをとった場合に長さLのものが全て作れる
dp[N] = [[INF] * 26, [0] * 26, 0]

for n in range(N-1,-1,-1):
    prev = dp[n+1]
    cur = copy.deepcopy(prev)
    s = S[n]
    cur[0][s] = n
    cur[1][s] = prev[2] // 26 + 1
    cur[2] = prev[2] + cur[1][s] - prev[1][s]
    dp[n] = cur

answer = []
i = 0
while i < N:
    # 辞書順で、作れる長さが一番短い文字
    L = dp[i][2] // 26
    for x in range(26):
        if dp[i][1][x] == L:
            break
    answer.append(chr(ord('a') + x))
    # その文字の場所に移動
    i = dp[i][0][x]
    i += 1

print(''.join(answer))

Submission status: Time Limit Exceeded

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

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

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

Solution code:
# coding:utf-8

import sys
from collections import Counter
import itertools

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


S = [ord(s) for s in S()]

used = set()
base1, base2 = 17, 19
# base = 17
length = min(Counter(S).values()) + 1
limit = 123 * (base2 ** length)
for s in S:
    tmp = set()
    for ss1, ss2 in used:
        ss1 = ss1 * base1 + s
        ss2 = ss2 * base2 + s
        if ss2 >= limit:
            continue

        if (ss1, ss2) not in used:
            tmp.add((ss1, ss2))

    used |= tmp

    if (s, s) not in used:
        used.add((s, s))

abc_n = [n for n in range(97, 123)]
for i in range(length):
    i += 1
    for nn in itertools.product(abc_n, repeat=i):
        tmp1 = 0
        tmp2 = 0
        for n in nn:
            tmp1 = tmp1 * base1 + n
            tmp2 = tmp2 * base2 + n
        if (tmp1, tmp2) not in used:
            ans = ''.join([chr(s) for s in nn])
            print(ans)
            exit()

print(-1)