You are given a string (|S| <= 10^5) and have to find such substring that repeats one after another maximum number of times. Or, if there are some such substrings, you must choose the longest/shortest/lexicografically_something.

For example: for test `bacacacb`

answer is `ac`

.

How to solve it? Thanks!

~~Make a suffix array, and an LCP array. Now your task is to find the longest non-zero contiguous subsequence in the LCP array, which can easily be done in linear time.~~edit: sorry, I thought it just said maximum number of occurrences.

`aclwawalaciac`

Your solution will give

`ac`

as an answer, but the correct answer is`wa`

.It seems that you didn't notice "such substring that repeats

one after anothermaximum number of times"