006 - Smallest Subsequence（★5）
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 5 点
問題文
英小文字のみからなる、長さ N の文字列 S が与えられます。
長さが K である S の部分列のうち、辞書順で最小であるものを出力してください。
注意
文字列 T の 部分列 とは、T から 0 個以上の文字を取り除いた後、残りの文字を元の順序を保ったまま連結して得られる文字列を指します。
「辞書順」での大小の定義
X = x_1 x_2 \ldots x_n, Y = y_1 y_2 \ldots y_m を二つの異なる文字列とするとき、X が Y の接頭辞であるか、j を x_j \neq y_j であるような最小の整数として x_j < y_j である場合、そしてその場合に限って「X は Y より辞書順で小さい」と言います。制約
- 1 \leq K \leq N \leq 100000
- S は英小文字のみからなる長さ N の文字列
- N, K は整数
入力
入力は以下の形式で標準入力から与えられます。
N K S
出力
答えとなる文字列を出力してください。
入力例 1
7 3 atcoder
出力例 1
acd
1, 3, 5 文字目のみを取り出すことで文字列 acd ができます。
この文字列はあり得る 3 文字の部分列のなかで辞書順最小です。
入力例 2
14 5 kittyonyourlap
出力例 2
inlap