Problem: 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.

Submission attempts (in order):

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



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



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



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


import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    inf = 10 ** 7
    s = input()
    n = len(s)
    s += "".join(chr(i + 97) for i in range(26))
    # print(s)
    
    size = [0] * 26
    pos = [n + i for i in range(26)]
    
    nxt = [-1] * n
    
    for i in range(n - 1, -1, -1):
        min_size = inf
        min_pos = -1
        
        
        for sz, p in zip(size, pos):
            if sz < min_size:
                min_size = sz
                min_pos = p
        code = ord(s[i]) - 97
        size[code] = min_size + 1
        pos[code] = i
        nxt[i] = min_pos
        # print(size)
        # print(pos)
        # print(nxt)
        # print()
    
    min_size = inf
    min_pos = -1
    for sz, p in zip(size, pos):
        if sz < min_size:
            min_size = sz
            min_pos = p
    i = min_pos
    ans = s[i]
    while i < n:
        i = nxt[i]
        ans += s[i]
    print(ans)

main()


import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    inf = 10 ** 7
    s = input()
    n = len(s)
    s += "".join(chr(i + 97) for i in range(26))
    # print(s)
    
    size = [0] * 26
    pos = [n + i for i in range(26)]
    
    nxt = [-1] * n
    
    for i in range(n - 1, -1, -1):
        min_size = inf
        min_pos = -1
        
        
        for sz, p in zip(size, pos):
            if sz < min_size:
                min_size = sz
                min_pos = p
        code = ord(s[i]) - 97
        size[code] = min_size + 1
        pos[code] = i
        nxt[i] = min_pos
        # print(size)
        # print(pos)
        # print(nxt)
        # print()
    
    min_size = inf
    min_pos = -1
    for sz, p in zip(size, pos):
        if sz < min_size:
            min_size = sz
            min_pos = p
    i = min_pos
    ans = s[i]
    while i < n:
        i = nxt[i]
        ans += s[i]
    print(ans)

main()


import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    inf = 10 ** 7
    s = input()
    n = len(s)
    s += "".join(chr(i + 97) for i in range(26))
    # print(s)
    
    size = [0] * 26
    pos = [n + i for i in range(26)]
    
    nxt = [-1] * n
    
    for i in range(n - 1, -1, -1):
        min_size = inf
        min_pos = -1
        
        
        for sz, p in zip(size, pos):
            if sz < min_size:
                min_size = sz
                min_pos = p
        code = ord(s[i]) - 97
        size[code] = min_size + 1
        pos[code] = i
        nxt[i] = min_pos
        # print(size)
        # print(pos)
        # print(nxt)
        # print()
    
    min_size = inf
    min_pos = -1
    for sz, p in zip(size, pos):
        if sz < min_size:
            min_size = sz
            min_pos = p
    i = min_pos
    ans = s[i]
    while i < n:
        i = nxt[i]
        ans += s[i]
    print(ans)

main()


import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    inf = 10 ** 7
    s = input()
    n = len(s)
    s += "".join(chr(i + 97) for i in range(26))
    # print(s)
    
    size = [0] * 26
    pos = [n + i for i in range(26)]
    
    nxt = [-1] * n
    
    for i in range(n - 1, -1, -1):
        min_size = inf
        min_pos = -1
        
        
        for sz, p in zip(size, pos):
            if sz < min_size:
                min_size = sz
                min_pos = p
        code = ord(s[i]) - 97
        size[code] = min_size + 1
        pos[code] = i
        nxt[i] = min_pos
        # print(size)
        # print(pos)
        # print(nxt)
        # print()
    
    min_size = inf
    min_pos = -1
    for sz, p in zip(size, pos):
        if sz < min_size:
            min_size = sz
            min_pos = p
    i = min_pos
    ans = s[i]
    while i < n:
        i = nxt[i]
        ans += s[i]
    print(ans)

main()


Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted

Accepted

Accepted

Accepted