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
- Let
dp(i, rem)be the minimum encoded length of the suffixs[i:]using at mostremdeletions. - Fix
s[i]as the first character of the next run and extend forward: characters equal tos[i]join the run, others must be deleted. - After extending by
j, the run length issame; its encoding costs 1 ifsame == 1, else1 + len(str(same)), and the rest isdp(j+1, rem - deleted). - Also consider deleting
s[i]outright viadp(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 justc, 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.