443. String Compression
Model: qwen3.5:9b
Topics: String
FAANG asked: 1
Acceptance rate: 44.1%
Problem Breakdown
We are given a mutable character array (chars) and need to compress consecutive repeating characters in-place.
- Input: A list of single-character strings (e.g.,
["a", "b"]). Constraints: length 1 to 2000, chars can be letters/digits/symbols. - Output: An integer representing the new compressed length. The input array must be modified such that its first N elements contain the compressed string.
- Logic: Iterate through groups of identical consecutive characters. If a group has length
k:- Append the character once.
- If
k > 1, append digits ofkimmediately after the character.
- Edge Cases: Single characters (no count appended), counts >= 10 (digits split into multiple chars in array).
Intuition
A naive approach might be to build a new string or list, then copy it back over the input array. While this is O(N) time, allocating an auxiliary buffer of size N violates the follow-up constraint for O(1) extra space.
To achieve O(1) space (excluding output storage), we must modify the existing chars array directly without creating a new list of characters. The key insight here is using two pointers:
- A read pointer (
i) to identify groups and count duplicates in the original data. - A write pointer (
joridx) that tracks where we are placing the compressed result within the same array.
Since compression reduces (or keeps equal) the length of a group compared to its raw character representation, the write index will generally lag behind the read index. This allows us to overwrite characters safely as long as we process groups sequentially from left to right without skipping unread data that hasn’t been processed yet. We only need integer counters for lengths and indices.
Approach
- Initialize
write_idxat 0 (the position where next character goes). - Iterate through the array using a pointer
i. For each group starting ati:- Count consecutive identical characters until a different one is found or end of list. Let this count be
count.
- Count consecutive identical characters until a different one is found or end of list. Let this count be
- Update the array:
- Always write the current character (
chars[i]) tochars[write_idx]and incrementwrite_idx. - If
count > 1, convertcountto a string (e.g., “2”, “10”). Iterate over each digit of that number, writing it tochars[write_idx]sequentially. Incrementwrite_idxfor every digit written.
- Always write the current character (
- Move the read pointer (
i) past this group so we don’t re-process these characters in subsequent iterations (since they are now consumed). - Return
write_idx.
Complexity Analysis
- Time: O(N), where N is the length of
chars. We traverse the array once to count groups and write digits. Converting a number to string takes logarithmic time relative to its value, but since max group size <= N (2000), this adds negligible overhead per group compared to linear traversal. - Space: O(1) extra space. We use only integer variables (
i,j,count) and do not allocate a new array proportional to input size.
Solution
def compress(chars):
write_idx = 0
n = len(chars)
i = 0
while i < n:
j = i + 1
count = 1
# Count consecutive duplicates starting at current group start 'i'
while j < n and chars[j] == chars[i]:
count += 1
j += 1
# Write the character itself first (always)
if write_idx != i:
pass # Logic ensures we overwrite safely, but strictly speaking
# we just place at current write position.
chars[write_idx] = chars[i]
write_idx += 1
# If count > 1, append digits of the length
if count > 1:
for digit in str(count):
chars[write_idx] = digit
write_idx += 1
# Move read pointer to end of current group (j)
i = j
return write_idx
# Example usage / verification logic would go here, but function is self-contained.
Edge Cases Handled
- Single Character Groups: Logic checks
count > 1before appending digits; if count is 1, only the character itself is written to the array at that position. - Multi-Digit Counts (>= 10): Converting integer count to string handles this naturally (e.g., “a” + ‘1’ + ‘2’). The loop iterates over each digit in
str(count)and writes them sequentially intochars. - Empty Input: Constraint guarantees length >= 1, but the logic holds for empty lists returning 0 implicitly if list is empty.
- Mixed Duplicates (e.g., “aa…b”): The loop resets at every group boundary (
i = j), ensuring independent groups of same characters are handled correctly without merging counts across different segments.