Encode String with Shortest Length

Hard

Given a string s, encode it so that its encoded length is as short as possible. The encoding rule is k[encoded_string], where encoded_string is repeated exactly k times. If encoding does not make the string shorter, keep it as-is. When several encodings share the minimum length, return the lexicographically smallest one.

Example 1

Input:  s = "aaa"
Output: "aaa"

Example 2

Input:  s = "aaaaa"
Output: "5[a]"

Example 3

Input:  s = "aaaaaaaaaa"
Output: "10[a]"

Constraints

• 1 <= s.length <= 12
• s consists of lowercase English letters only.