⚡Flashcard Drill➔
NeetCode #752LC-1531Hard2-D Dynamic Programming
← Back to All Problems

#752 · #1531 · String Compression II(压缩字符串 II)

📌 Problem Statement & Constraints

Run-length encoding replaces a run of L identical characters c with c if L == 1, else c followed by the decimal digits of L. Given a string s and an integer k, delete at most k characters to minimise the encoded length, and return that minimum. Constraints: 1 <= s.length <= 100, 0 <= k <= s.length.

💡 Core Algorithmic Approaches

  1. Let dp(i, rem) be the minimum encoded length of the suffix s[i:] using at most rem deletions.
  2. Fix s[i] as the first character of the next run and extend forward: characters equal to s[i] join the run, others must be deleted.
  3. After extending by j, the run length is same; its encoding costs 1 if same == 1, else 1 + len(str(same)), and the rest is dp(j+1, rem - deleted).
  4. Also consider deleting s[i] outright via dp(i+1, rem-1), and memoise on (i, rem).

💻 Benchmark Python3 Implementation

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dp(i: int, rem: int) -> int:
            if i == len(s):
                return 0
            if rem < 0:
                return float("inf")
            best = float("inf")
            same = 0
            deleted = 0
            j = i
            while j < len(s):
                if s[j] == s[i]:
                    same += 1
                else:
                    deleted += 1
                if deleted > rem:
                    break
                cost = 1 if same == 1 else 1 + len(str(same))
                best = min(best, cost + dp(j + 1, rem - deleted))
                j += 1
            # alternatively, delete s[i] itself
            best = min(best, dp(i + 1, rem - 1))
            return best

        return dp(0, k)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2 * k): O(n * k) memoised states, each scanning up to O(n) characters.
💾 Space Complexity
O(n * k) for the memo table plus O(n) recursion depth.

⚠️ Interview Pitfalls & Follow-ups

  • Assuming deletions only remove characters: deletions also shrink runs, which can change an encoding from c + digits down to just c, so run lengths must be recomputed.
  • Off-by-one in the encoding cost: a run of length 1 costs 1, while length at least 2 costs 1 + len(str(L)); forgetting the leading character overcounts.
  • Deleting greedily: which characters to delete interacts with the run structure, so a DP over suffixes is required.
  • Not guarding rem < 0: without the guard the recursion explores invalid states and the memoisation key becomes meaningless.
⚡
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 2-D Dynamic Programming Problems