The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets

Note:

k will be a positive integer and encoded string will not be empty or have extra space. You may

Example 1:

Input: "aaa" Output: "aaa" Explanation: There is no way to encode it such that it is shorter

Example 2:

Input: "aaaaa" Output: "5[a]" Explanation: "5[a]" is shorter than "aaaaa" by 1 character.

Example 3:

Input: "aaaaaaaaaa" Output: "10[a]" Explanation: "a9[a]" or "9[a]a" are also valid solutions,

Example 4:

Input: "aabcaabcd" Output: "2[aabc]d" Explanation: "aabc" occurs twice, so one answer can be

Example 5:

Input: "abbbabbbcabbbabbbc" Output: "2[2[abbb]c]" Explanation: "abbbabbbc" occurs twice, but

Solution: O(N ^ 4) Maintain a 2d String array of minimum substring and split each substring