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

  1. Scan for maximal runs of identical characters with two pointers.
  2. For each run, write the character and then the decimal digits of its length (only when the length exceeds 1).
  3. Collect the output in a list and copy it back into chars, which avoids the index arithmetic of writing in place while scanning.
  4. Note that the digits of a multi-digit length are separate characters, so 12 contributes '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, which chars[:n] = res would then treat as a single element. Use extend(list(str(cnt))).
  • Not writing the result back into chars: the judge reads the first k characters of chars.
  • Advancing i by 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.
🎯 Drill This Card Now➔

🧩 Related Two Pointers Problems