NeetCode #710LC-471Hard1-D Dynamic Programming
← Back to All Problems#710 · #471 · Encode String with Shortest Length(编码最短长度的字符串)
📌 Problem Statement & Constraints
Given a string
s, return its shortest encoded form, where a substring that repeats k times may be written as k[encoded]. If the encoding is not shorter than the original, keep the original. Constraints: 1 <= s.length <= 150, and s consists of lowercase English letters.💡 Core Algorithmic Approaches
- Let
dp[i][j]be the shortest encoding ofs[i..j]; a single character encodes to itself. - For a longer range, either concatenate the encodings of two parts at a split point, or encode the whole range as
k[block]if it is a repetition of a smaller block. - Repetition is detected with a rotation check: the period is
(t + t).find(t, 1), and if that is less than the length, the block repeats. - Use the already-computed
dp[i][i+period-1]as the inner encoding so the block itself is optimised.
💻 Benchmark Python3 Implementation
class Solution:
def encode(self, s: str) -> str:
n = len(s)
dp = [[""] * n for _ in range(n)]
for length in range(1, n + 1):
for i in range(n - length + 1):
j = i + length - 1
sub = s[i:j + 1]
dp[i][j] = sub # start with the raw substring
if length > 4:
t = sub
pos = (t + t).find(t, 1)
if pos < len(t): # t is a repetition of its period
cnt = len(t) // pos
cand = str(cnt) + "[" + dp[i][i + pos - 1] + "]"
if len(cand) < len(dp[i][j]):
dp[i][j] = cand
for k in range(i, j):
cand = dp[i][k] + dp[k + 1][j]
if len(cand) < len(dp[i][j]):
dp[i][j] = cand
return dp[0][n - 1]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^3) with O(n) substring work, effectively O(n^4); fine for n <= 150.
💾 Space Complexity
O(n^2): the DP table.
⚠️ Interview Pitfalls & Follow-ups
- Applying the repetition check only for long substrings: encodings shorter than five characters never benefit from a
k[...]wrapper, so thelength > 4prune is safe but must be understood. - Searching with
.find(t)without an offset: that always returns 0, so the period search needs.find(t, 1). - Considering only repetition or only splitting: the optimum may combine both, so both must be evaluated.
- Keeping an encoding that is not shorter: the encoded form is only used when it is strictly shorter than the raw substring.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.