NeetCode #196LC-443MediumTwo Pointers
← Back to All Problems#196 · #443 · String Compression(压缩字符串)
📌 Problem Statement & Constraints
Given an array of characters
chars, compress it in place using run-length encoding: for each group of consecutive identical characters, write the character followed by the group length (omitted when the length is 1). Return the new length. Constraints: 1 <= chars.length <= 2000; chars[i] is a lowercase letter, uppercase letter, digit or symbol.💡 Core Algorithmic Approaches
- Scan for maximal runs of identical characters with two pointers.
- For each run, write the character and then the decimal digits of its length (only when the length exceeds 1).
- Collect the output in a list and copy it back into
chars, which avoids the index arithmetic of writing in place while scanning. - Note that the digits of a multi-digit length are separate characters, so
12contributes'1'and'2'.
💻 Benchmark Python3 Implementation
class Solution:
def compress(self, chars: List[str]) -> int:
res = []
i = 0
n = len(chars)
while i < n:
ch = chars[i]
j = i
while j < n and chars[j] == ch:
j += 1 # end of the run
cnt = j - i
res.append(ch)
if cnt > 1:
res.extend(list(str(cnt))) # digits are separate characters
i = j
chars[:len(res)] = res # write back in place
return len(res)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each character is visited once, and the write-back is linear in the compressed length.
💾 Space Complexity
O(k) for the output buffer, where k is the compressed length.
⚠️ Interview Pitfalls & Follow-ups
- Writing the count when it is 1: a single character is written alone, with no digit.
- Appending the count as a whole number:
res.append(str(cnt))would append a multi-character string, whichchars[:n] = reswould then treat as a single element. Useextend(list(str(cnt))). - Not writing the result back into
chars: the judge reads the firstkcharacters ofchars. - Advancing
iby 1 instead of to the run end: this re-processes the run.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.