407883: GYM102916 G Lexicographically Minimal Subsequence

You 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.