Compute shortest recursive string encoding

Given a string s, compress it by replacing any consecutive repetition of a substring with the form k{pattern} where k > 1 and pattern may itself be recursively encoded. Return the shortest possible encoded string; if no encoding shortens s, return s unchanged. Clearly define the encoding rules, implement a function encode(s) that outputs the minimal-length encoding, and analyze time and space complexity. Discuss how you detect repeat structure, handle nested encodings, and avoid redundant work.

Compute Shortest Recursive String Encoding

Given a string s, compress it by replacing any consecutive repetition of a substring with the form k{pattern}, where k > 1 is the repeat count and pattern may itself be recursively encoded. Return the shortest possible encoded string. If no encoding makes the string strictly shorter, return s unchanged.

Encoding rules

• A run of k (k > 1) consecutive copies of some pattern may be written as k{pattern}.
• pattern inside the braces may itself be encoded recursively (nested encodings are allowed).
• An encoding is only used when it is strictly shorter than the literal substring it replaces. Among all valid encodings, return one of minimal total length.
• Plain characters are written as-is; encodings are simply concatenated (e.g. 2{aabc}d).

Examples

• encode("aaaaa") = "5{a}" (5 chars → 4 chars).
• encode("aaaa") = "aaaa" — 4{a} is also 4 chars, not shorter, so the original is returned.
• encode("aabcaabcd") = "2{aabc}d" (9 chars → 8 chars).
• encode("abbbabbbcabbbabbbc") = "2{2{abbb}c}" — the inner abbbabbbc itself encodes to 2{abbb}c, demonstrating nesting.

Implement encode(s), explain how you detect repeat structure, how nested encodings are handled, and analyze time and space complexity.

Constraints

• 1 <= len(s) <= 150 (typical interview / LC 471 bound)
• s consists of lowercase English letters only
• k in k{pattern} is always greater than 1; an encoding is used only when strictly shorter
• Nested encodings are permitted: the pattern inside braces may itself be encoded

Hints

1. Think interval DP: let dp[i][j] be the shortest encoding of the substring s[i..j]. Combine answers from splitting at every interior point.
2. To test whether a substring is a pure repetition of some unit, use the classic trick: a string t repeats iff t is a substring of (t + t) starting at an index in (0, len(t)). Or just check each divisor length of len(t).
3. When a substring is a repetition k copies of unit, its candidate encoding is str(k) + '{' + encode(unit) + '}' — recurse on the unit so nested patterns are captured.
4. Only replace with k{pattern} when it is STRICTLY shorter than the literal text; otherwise keep the literal (that is why 'aaaa' stays 'aaaa' but 'aaaaa' becomes '5{a}').
5. Evaluate the full-string repetition candidate before the split candidates so that on length ties the cleaner full-string form (e.g. '10{a}') is preferred over a split like 'a9{a}'.