Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Who Doesn't Love Shorter Strings?

By Reyad18 · Limits 1s, 512 MB

I hope you are not someone who hates longer strings, or fears longer strings like me. Strings can be a nightmare at any day of your competitive programming life. Hence, in this problem, we want to encode longer strings to shorter lengths. You will be given a string and the encoding rule is: x[encoded_string], where the encoded_string inside the square brackets is being repeated exactly x times. You can take any substring of the main string and replace it with it's encoded version. For example, you can take substring "aaaa" from "baaaa" and replace it with "4[a]", so the string will be " b4[a]". x should be a positive integer.

Input

You will be given a string ss consisting lowercase English letters. The length of the string will be between 11 to 300300.

Output

Print the shortest string achievable by encoding. If there are several solutions, return the lexicographically smallest one.

Samples

InputOutput
aaa
aaa

Can be encoded to 3[a], but it has more characters. So, original string is the shortest string achievable.

InputOutput
aabaabcaabaabc
2[2[aab]c]

    Discussion

    Statistics


    0% Solution Ratio

    Submit

    Login to submit

    Editorial

    I will come to the lexicographical part later. Let's take a look at this from the top down. There ar...

    Toph uses cookies. By continuing you agree to our Cookie Policy.