Dense Subsequence
Contest: Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)
Difficulty rating: 1900
Tags: data structures, greedy, strings

You are given a string s, consisting of lowercase English letters, and the integer m.

One should choose some symbols from the given string so that any contiguous subsegment of length m has at least one selected symbol. Note that here we choose positions of symbols, not the symbols themselves.

Then one uses the chosen symbols to form a new string. All symbols from the chosen position should be used, but we are allowed to rearrange them in any order.

Formally, we choose a subsequence of indices 1 ≤ i1 < i2 < ... < it ≤ |s|. The selected sequence must meet the following condition: for every j such that 1 ≤ j ≤ |s| - m + 1, there must be at least one selected index that belongs to the segment [j,  j + m - 1], i.e. there should exist a k from 1 to t, such that j ≤ ik ≤ j + m - 1.

Then we take any permutation p of the selected indices and form a new string sip1sip2... sipt.

Find the lexicographically smallest string, that can be obtained using this procedure.

Input format:
The first line of the input contains a single integer m (1 ≤ m ≤ 100 000).

The second line contains the string s consisting of lowercase English letters. It is guaranteed that this string is non-empty and its length doesn't exceed 100 000. It is also guaranteed that the number m doesn't exceed the length of the string s.

Output format:
Print the single line containing the lexicographically smallest string, that can be obtained using the procedure described above.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, one can choose the subsequence {3} and form a string "a".

In the second sample, one can choose the subsequence {1, 2, 4} (symbols on this positions are 'a', 'b' and 'a') and rearrange the chosen symbols to form a string "aab".

Example input:
3
cbabc

Example output:
a

Example input:
2
abcab

Example output:
aab

Editorial:
It is not hard to see that if we choose some subset of the letters then to achieve lexicographically smallest string you must first write all of the letters 'a', then all of the letters 'b' and so on.
Let's assume that the string in the answer consists only of the letters 'a'. Then it should be as small of them as possible to get lexicographically smallest string. We can check whether it is enough to take only the letters 'a' to meet the requirement on the density of the indices (in each subsegment of length m it has to be at least one letter 'a'). If this is true, we can find the minimum number of letters 'a', which will satisfy the density requirement, using the greedy algorithm (every time we will take the rightmost letter 'a', which is separated from the previous one by no more than m positions). If this is not true, then the answer must contain some other letters except for 'a'. This means that we need to take as much 'a' letters as possible. So we can take all of them, because adding any additional letter will not affect the density requirement.
Then do the same with the letter 'b', bearing in mind that all of the letters 'a' is already taken. If the letters 'b' is not enough, then take all of the letters 'a', all of the letters 'b' and proceed to the next letter, and so on.