CTU Open Contest 2018 - Locker Room

View as PDF

Submit solution

Points: 20
Time limit: 3.0s
Memory limit: 256M

Problem type

There are several strange rooms in Binary Casino and one of them is a locker room. You have to enter the locker room several times a day, two times being a minimum (before and after your shift). There is no key or access code needed to enter the locker room. There is a brand new security lock system instead.

The lock system presents you with a generated puzzle which you have to solve every time you want to enter the locker room. This system prevents possible intruders to enter the locker room, as the puzzle takes them a long time to solve. Only employees, after working in the casino for some time, manage to master the puzzle.

It is your second week in the casino and you have already been late three times because you didn't manage to solve the puzzle quickly enough. You therefore decided to write a program which solves the puzzle. The puzzle is as follows:

You are given a cyclic string of N lowercase english letters. You have to choose and mark substrings (continuous segments of characters) of a given length K until each character in the string is marked. Marking a substring does not change the original string and each character can be marked multiple times. The task is to print the lexicographically maximal substring among chosen substrings. In addition, the printed substring has to be lexicographically minimal possible.

For example, let acdb be the given string of length N = 4 and let K = 3. Then you can choose substrings acd and bac to mark the whole string. The puzzle solution is bac.

Input Specification

The first line of input contains two integers N and K (1 \le N \le 5 \cdot 10^5, 1 \le K \le N), describing the length of the given string and the length of marked substrings. The second line contains N lowercase english letters – the given cyclic string.

Output Specification

Output the lexicographically maximal substring among chosen substrings under the condition the result is lexicographically minimal possible.

Sample Input 1

4 3
acdb

Sample Output 1

bac

Sample Input 2

6 2
aababa

Sample Output 2

ab

Sample Input 3

10 4
abaaabaaba

Sample Output 3

aaba
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.