288. Encode String with Shortest Length

HardString String

Given a string s, encode it such that its encoded length is the shortest, using the rule k[encoded_string] (the inner string repeated k times). Return the length of the shortest possible encoding. Encoding is only beneficial when it shortens the string.

Input: A quoted string s.

Output: Integer — shortest encoded length.

Examples

Example 1

Input: "aaaaaaaaaa"
Output: 5
Explanation: '10[a]' has length 5.

Example 2

Input: "aaa"
Output: 3
Explanation: Encoding doesn't help.

Example 3

Input: "abbbabbbcabbbabbbc"
Output: 11
Explanation: Best nested encoding.

Constraints

1<=s.length<=150

Asked by

Google

Solve this problem in the editor →