Encode String with Shortest Length - Video Solutions
LeetCode 471. Encode String with Shortest Length
Encode String with Shortest Length - Video Solution
Watch 3 video solutions for Encode String with Shortest Length, a hard level problem involving String, Dynamic Programming. This walkthrough by Happy Coding has 4,893 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Given a string s, encode the string such that its encoded length is the shortest.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. k should be a positive integer.
If an encoding process does not make the string shorter, then do not encode it. If there are several solutions, return any of them.
Example 1:
Input: s = "aaa" Output: "aaa" Explanation: There is no way to encode it such that it is shorter than the input string, so we do not encode it.
Example 2:
Input: s = "aaaaa" Output: "5[a]" Explanation: "5[a]" is shorter than "aaaaa" by 1 character.
Example 3:
Input: s = "aaaaaaaaaa" Output: "10[a]" Explanation: "a9[a]" or "9[a]a" are also valid solutions, both of them have the same length = 5, which is the same as "10[a]".
Constraints:
1 <= s.length <= 150sconsists of only lowercase English letters.
Approach Overview
Problem Overview: You receive a string and must encode it into the shortest possible representation using the pattern k[encoded_string], where the substring inside brackets repeats exactly k times. The goal is to minimize the final encoded length while preserving the original string when decoded.
Approach 1: Brute Force Substring Enumeration (Exponential Time, O(2^n) time, O(n) space)
Generate every possible partition of the string and attempt to compress repeating segments using the k[pattern] format. For each substring, check if it consists of repeated copies of a smaller substring. This approach repeatedly recomputes encodings for the same substrings and quickly becomes infeasible as string length grows. It helps illustrate the core idea of detecting repetition but does not scale beyond small inputs.
Approach 2: Dynamic Programming on Substrings (O(n^3) time, O(n^2) space)
Define dp[i][j] as the shortest encoded string for substring s[i..j]. Iterate over substring lengths and try every split point k between i and j, combining dp[i][k] and dp[k+1][j]. Then check if the entire substring is a repetition of some smaller pattern. If it is, encode it as count[encoded_pattern]. This avoids recomputation because every substring result is stored and reused. The nested substring iteration leads to O(n^3) time complexity.
Approach 3: DP with Efficient Repetition Detection (O(n^3) time, O(n^2) space)
Use the same DP table but detect repeating patterns efficiently. For substring t, compute (t + t).find(t, 1) to determine whether a shorter repeating unit exists. If the index returned is less than the substring length, the substring is periodic and can be encoded as k[dp[i][i+pattern_len-1]]. This trick quickly identifies repeating structures like ababab or aaaa. Combined with DP splitting, it guarantees the globally shortest encoding.
Recommended for interviews: The dynamic programming approach with substring repetition detection is the expected solution. It demonstrates strong understanding of dynamic programming and efficient pattern detection within string problems. Explaining the brute force idea first shows intuition, but implementing the dp[i][j] solution proves you can optimize overlapping subproblems and recognize repeated string structures.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Encoding | O(2^n) | O(n) | Conceptual understanding of repetition detection; impractical for large inputs |
| Dynamic Programming with Split Enumeration | O(n^3) | O(n^2) | General solution that guarantees shortest encoding |
| DP with Repetition Detection Trick | O(n^3) | O(n^2) | Best practical approach; quickly detects repeating patterns and minimizes encoded length |