典型90【006 – Smallest Subsequence（★5）】をpython解説

import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

N,K = MI()
letter = S()

# ord('a')→97
# chr(97)→a
INF = 10**18
dp = [[INF for i in range(26)] for i in range(N+1)]
#N+1行目は、使わないけど、dp[i][j]=dp[i+1][j]とするときに必要になる

for i in range(N-1,-1,-1):#後ろからみる
    for j in range(26):#a~zの26もじについて
        dp[i][j] = dp[i+1][j]#i文字目以降でj番目のアルファベットがはじめて出てくるのは、
    dp[i][ord(letter[i]) - ord("a")] = i#i文字目がj番目のアルファベットのときのみ、= i

ans = ""
cnt = 0
now = 0
while cnt !=K:#文字列の長さはKになるまで
    for j in range(26):#辞書順最小のaから順に
        if N - dp[now][j] >= K-cnt:
            #now番目の文字にアルファベットj番目の文字を使用したとき
            # もし、N-dp[now][j](残り使える文字数) >= K-cnt(目標の文字列までの数)ならok
            ans += chr(ord('a') + j)
            #次の探索範囲は、現在使用した文字のindex+1からなので
            now = dp[now][j] + 1
            #文字列カウント+1
            cnt += 1
            break
print(ans)