abc 097 c (python)

文字列 s から作られる部分列の中で辞書順で k 番目に小さいものを求める問題。
k <= 5 と k の制約がかなり小さかったので、s の中から a から始まるもの、b から始まるもの、…と探していって、あるアルファベットまでで始まる部分列が累計 k 個以上たまったらそこで探索終了するプログラムを書いた。k = 500, len(s) = 5000 でも全然間に合いそう。

import sys
input = sys.stdin.readline
s = input().rstrip()
l = len(s)
k = int(input())
chk = set()
for i in range(26):
  for j in range(l):
    if s[j] == chr(i+97):
      for m in range(min(k,l-j)):
        chk.add(s[j:j+1+m])
  if len(chk) >= k:
    break
    
chk = sorted(list(chk))
print(chk[k-1])