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


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


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


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


from string import ascii_lowercase
from bisect import bisect


def solve(s):
    pos = [[] for _ in range(26)]
    offset = ord('a')
    for i, c in enumerate(s):
        c = ord(c) - offset
        pos[c].append(i)
    for l in pos:
        l.append(len(s))

    all_char_sequence_start_pos = []
    pos_i = [len(l) - 1 for l in pos]
    while all(pi >= 0 for pi in pos_i):
        i = min(l[pi] for pi, l in zip(pos_i, pos))
        all_char_sequence_start_pos.append(i)
        for j in range(26):
            while pos_i[j] >= 0 and pos[j][pos_i[j]] >= i:
                pos_i[j] -= 1
    all_char_sequence_start_pos.reverse()
    ans = []
    curr = -1
    for i in all_char_sequence_start_pos:
        for c in range(26):
            cj = bisect(pos[c], curr)
            j = pos[c][cj]
            if j >= i:
                ans.append(c)
                curr = j
                break
    return ''.join(chr(c + offset) for c in ans)


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


from string import ascii_lowercase
from bisect import bisect


def solve(s):
    pos = [[] for _ in range(26)]
    offset = ord('a')
    for i, c in enumerate(s):
        c = ord(c) - offset
        pos[c].append(i)
    for l in pos:
        l.append(len(s))

    all_char_sequence_start_pos = []
    pos_i = [len(l) - 1 for l in pos]
    while all(pi >= 0 for pi in pos_i):
        i = min(l[pi] for pi, l in zip(pos_i, pos))
        all_char_sequence_start_pos.append(i)
        for j in range(26):
            while pos_i[j] >= 0 and pos[j][pos_i[j]] >= i:
                pos_i[j] -= 1
    all_char_sequence_start_pos.reverse()
    ans = []
    curr = -1
    for i in all_char_sequence_start_pos:
        for c in range(26):
            cj = bisect(pos[c], curr)
            j = pos[c][cj]
            if j >= i:
                ans.append(c)
                curr = j
                break
    return ''.join(chr(c + offset) for c in ans)


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


from string import ascii_lowercase
from bisect import bisect


def solve(s):
    pos = [[] for _ in range(26)]
    offset = ord('a')
    for i, c in enumerate(s):
        c = ord(c) - offset
        pos[c].append(i)
    for l in pos:
        l.append(len(s))

    all_char_sequence_start_pos = []
    pos_i = [len(l) - 1 for l in pos]
    while all(pi >= 0 for pi in pos_i):
        i = min(l[pi] for pi, l in zip(pos_i, pos))
        all_char_sequence_start_pos.append(i)
        for j in range(26):
            while pos_i[j] >= 0 and pos[j][pos_i[j]] >= i:
                pos_i[j] -= 1
    all_char_sequence_start_pos.reverse()
    ans = []
    curr = -1
    for i in all_char_sequence_start_pos:
        for c in range(26):
            cj = bisect(pos[c], curr)
            j = pos[c][cj]
            if j >= i:
                ans.append(c)
                curr = j
                break
    return ''.join(chr(c + offset) for c in ans)


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


from string import ascii_lowercase
from bisect import bisect


def solve(s):
    pos = [[] for _ in range(26)]
    offset = ord('a')
    for i, c in enumerate(s):
        c = ord(c) - offset
        pos[c].append(i)
    for l in pos:
        l.append(len(s))

    all_char_sequence_start_pos = []
    pos_i = [len(l) - 1 for l in pos]
    while all(pi >= 0 for pi in pos_i):
        i = min(l[pi] for pi, l in zip(pos_i, pos))
        all_char_sequence_start_pos.append(i)
        for j in range(26):
            while pos_i[j] >= 0 and pos[j][pos_i[j]] >= i:
                pos_i[j] -= 1
    all_char_sequence_start_pos.reverse()
    ans = []
    curr = -1
    for i in all_char_sequence_start_pos:
        for c in range(26):
            cj = bisect(pos[c], curr)
            j = pos[c][cj]
            if j >= i:
                ans.append(c)
                curr = j
                break
    return ''.join(chr(c + offset) for c in ans)


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


Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted

Accepted

Accepted

Accepted