Compute shortest recursive string encoding
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
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.
Quick Answer: This question evaluates proficiency in string manipulation, pattern detection, recursion, and dynamic programming for efficient sequence compression in the Coding & Algorithms domain.
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
Examples
Input: ("aaa",)
Expected Output: "aaa"
Explanation: '3{a}' is 4 chars, longer than the 3-char original, so the string is returned unchanged.
Input: ("aaaaa",)
Expected Output: "5{a}"
Explanation: Five 'a's compress to '5{a}' (4 chars < 5).
Hints
- 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.
- 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).
- 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.
- 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}').
- 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}'.