Atcoder典型90問 006 - Smallest Subsequence

Atcoder典型90問 006 - Smallest Subsequence（★5）

▶︎https://atcoder.jp/contests/typical90/tasks/typical90_f

問題

英小文字のみからなる、長さ
N の文字列
S が与えられます。

長さが
K である
S の部分列のうち、辞書順で最小であるものを出力してください。

制約

1≤K≤N≤100000\\
S は英小文字のみからなる長さ N の文字列\\
N,K は整数

試したこと

• 辞書は左から貪欲法。
  • 文字列のなかで辞書順が小さいアルファベットから順に探索していき、右側に残りの文字数分だけ文字列がとれるか調べれば良い。取れる場合はその文字を採用し、取れない場合は採用せずに次の文字に行く。
  • 文字を採用した場合、のこり選択回数を1減らし、その文字より右の文字列に対して再探索。
• 計算量やばいかなーと思ったら案の定やばくてTLE。
  • 再帰で書いたのもよくなかったのかもしれない。
  • よく考えたら再帰する必要ないな...
• アルゴリズム自体は容易に実装できたが、TLEの回避方法がわからなかった。挫折。

適切な方針

• 前処理を行う。

解説付きコード

コードは https://drken1215.hatenablog.com/entry/2021/10/10/195200　　
から引用させていただきました。大変わかりやすい解説がついていて参考になりました。

# res[i][c] := i 文字目以降で最初に文字 c が登場する index
# 存在しないときは N
def calc_next(S):
    # 文字列 S の長さ
    N = len(S)

    # 答え
    res = [[N] * 26 for _ in range(N + 1)]

    # 後ろから見る
    for i in range(N - 1, -1, -1):
        # i + 1 文字目以降の結果を一旦 i 文字にコピー
        for j in range(26):
            res[i][j] = res[i + 1][j]

        # i 文字目の情報を反映させる
        res[i][ord(S[i]) - ord('a')] = i

    # 答えを返す
    return res

# 入力
N, K = map(int, input().split())
S = input()

# 前処理
res = ''
nex = calc_next(S)

# 貪欲法
j = -1
for i in range(K):
    for ordc in range(26):
        k = nex[j + 1][ordc]

        # ちゃんと K 文字が作れれば OK
        if N - k >= K - i:
            res += chr(ord('a') + ordc)
            j = k
            break
print(res)

TLEしたコード

def findAvailableSmallest(S, k, selected_s):
  if k == 0:
    return(S, k, selected_s)
  
  if len(S) == k:
    for i in range(len(S)):
      selected_s.append(S[i])
    return(S, k, selected_s)
  
  Slist = list(S)
  Slist.sort()
  for s in Slist:
    s_place = S.find(s)
    if s_place + k> len(S):
      continue
    else:
      selected_s.append(s)
      [S, k, selected_s] = findAvailableSmallest(S[s_place+1:], k-1, selected_s)
      break
  
  return(S, k, selected_s)
 
[N, K] = list(map(int, input().split()))
S = input()
selected_s = []
[S, K, selected_s] = findAvailableSmallest(S, K, selected_s)
 
print("".join(selected_s))