Codeforces724 D. Dense Subsequence(字符串贪心)

D. Dense Subsequence time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

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 ≤ i₁ < i₂ < ... < i_t ≤ |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 ≤ i_k ≤ j + m - 1.

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

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

Input

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

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

Examples Input 3 cbabc Output a Input 2 abcab Output aab Input 3 bcabcbaccba Output aaabb 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".

题意：有一个由小写字母组成的字符串s和一个整数m，现在要选出一个子串1 ≤ i₁ < i₂ < ... < i_t ≤ |s|，使得1<=j<=|s|-m+1时，j<=ik<=j+m-1， 输出排序后字典序最小的子串。

例如

2 abcab

“ab”选a，"bc"选b， "ca"选a，"ab"还是上一次选中的a，所以结果是aab

思路：每m个里面选择字典序最小的字符，当从[i,i+m-1]中选了一个字符下标为p，那么下一次i就从p+1开始，从[p+1, p+m]中选。

要注意如果是有多个最小的字符，要选最右的一个，例如m=4, s=bzzbzzz, 如果选第一个b结果就是bb，选后面那个结果就是b。

以上过程记录选中的最大字符，然后把s中还没被选中并且比最大字符小的字符加到子串中，因为最大字符尽量少取，其余的尽量多取，abbbc比ac小。

#include <bits/stdc++.h> using namespace std; #define maxn 100010 int v[30]; char s[maxn]; int main() { int len, m, i, j, t; scanf("%d", &m); scanf("%s", s+1); len = strlen(s+1); char maxx = 'a'; for(i = 1;i <= len-m+1;i++){ char u = 'z'; int p = -1; for(j = i;j <= i+m-1;j++){ if(s[j]<=u){ u = s[j]; p = j; } } if(p!=-1){ v[u-'a']++; s[p] = '.'; if(u > maxx) maxx = u; i = p; } } for(i = 1;i <= len;i++){ if(s[i]!='.'&&s[i]<maxx) v[s[i]-'a']++; } for(i = 0;i < 26;i++){ while(v[i]--) printf("%c", i+'a'); } printf("\n"); }