U517305 「ALFR Round 3」C Division

[Chinese Statement](P11447). The hack data is only in the Chinese version.

Let $f(S)$ denote the lexicographically largest subsequence of the string $S$. Given an integer $k$, you need to divide the original string $S$ into $k$ substrings, where the $i$-th substring is denoted as $a_i$. The weight of a partition scheme is defined as $\max f(a_i)$ for $1 \leq i \leq k$. Since there are many partition schemes, you are required to find the **lexicographically smallest weight** among all possible partition schemes. **Note**: The term "weight" here refers to a string. Definition of Subsequence: A subsequence of a sequence is formed by removing some elements from the original sequence without changing the relative positions of the remaining elements. Definition of Lexicographical Order: In lexicographical order, two strings are compared starting from the first character. If the characters differ, the string with the smaller first character is smaller. If the characters are the same, the comparison continues with the next character, and so forth, until all characters are compared. If one string is a prefix of another, the shorter string is considered smaller.

无

无

In the sample, you can divide the string $S$ into `sky` and `aqua` as the $2$ substrings. The functions $f$ for these strings are `y` and `ua`, respectively; thus, the maximum of $f$ values is `y`. It can be proven that `y` is the lexicographically smallest weight among all partition schemes. | Subtask | Score | Constraints | | :----------: | :----------: | :----------: | | $1$ | $10$ | $n \leq 10$ | | $2$ | $20$ | $n \leq 10^2$ | | $3$ | $20$ | $n \leq 3 \times 10^2$ | | $4$ | $10$ | All characters in the string $S$ are guaranteed to be equal | | $5$ | $10$ | $k=1$ | | $6$ | $30$ | - | For all the tests, $1 \leq k \leq n \leq 2 \times 10^5$, and the characters in the string $S$ are all lowercase letters.