시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 26 | 16 | 16 | 72.727% |
Your are given a string $s$ and an integer $k$. Find the lexicographically minimal subsequence of $s$ which length is $k$.
The first line contains a string $s$ ($1 \le |s| \le 10^6$). It consists of lowercase Latin letters.
The second line contains an integer $k$ ($1 \le k \le |s|$) --- the length of the resulting subsequence.
Output the lexicographically minimal subsequence of $s$ which length is $k$.
bcaabac 4
aaac
String $s_{p_{1}}s_{p_{2}}\dots s_{p_{k}} (1 \le p_{1} < p_{2} < \dots < p_{k} \le |s|)$ is called a subsequence of string $s$.
String $x = x_{1}x_{2}\dots x_{k}$ is lexicographically less than string $y = y_{1}y_{2}\dots y_{k}$, if there exists such number $i$ $(1 \le i \le k)$, that $x_{1} = y_{1}, x_{2} = y_{2}, \ldots , x_{i-1} = y_{i-1}$ and $x_{i} < y_{i}$. Characters in strings are compared as their ASCII codes.