⚡Flashcard Drill➔
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

  1. Let dp[i][j] be the shortest encoding of s[i..j]; a single character encodes to itself.
  2. 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.
  3. 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.
  4. 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 the length > 4 prune 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.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems