String Compression
Problem
Given an array of characters chars, compress it in-place such that consecutive groups of the same character are replaced by the character followed by the group's length, and return the new length of the array after compression.
- 1 ≤ chars.length ≤ 2000
- chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol.
Example
chars = ["a","a","b","b","c","c","c"]6The groups are "aa", "bb", and "ccc". After compression, the array becomes ["a","2","b","2","c","3"]. The new length is 6. The algorithm scans the array, counts consecutive characters, writes the character once, and if the count is greater than 1, writes the count digits sequentially. This in-place approach avoids extra space by using two pointers: one to read and one to write.
Approach
Straightforward Solution
A naive approach would build a new string or array to store the compressed result, which uses extra space and violates the in-place constraint. Another brute-force approach might repeatedly shift elements, resulting in O(n²) time complexity.
Core Observation
Compression depends on identifying consecutive groups of identical characters and replacing them with the character plus the count if greater than one. The key is to perform this in-place, which requires careful management of read and write pointers to avoid overwriting unprocessed data.
Path to Optimal
The insight is to use two pointers: one to iterate through the input array (read pointer) and one to track the position to write compressed characters (write pointer). For each group of identical characters, count its length, write the character once, and if count > 1, write each digit of the count sequentially. This approach ensures a single pass with O(n) time and O(1) extra space.
Optimal Approach
Iterate through the array with a read pointer. For each group of identical characters, count its length by advancing the read pointer. Write the character at the write pointer, increment write. If count > 1, convert count to string and write each digit at the write pointer, incrementing write accordingly. Return the write pointer as the new length.
Time
O(n)
Each character is visited at most twice: once by the read pointer to count groups, and once by the write pointer to write compressed characters, resulting in linear time.
Space
O(1)
The algorithm uses only a fixed number of pointers and variables for counting and writing, modifying the input array in-place without additional data structures.
Pattern Spotlight
Two Pointers (In-Place Compression)
Use one pointer to read and count groups, and another to write compressed output in-place, ensuring no data loss or overwriting by carefully advancing pointers only after processing each group.
Solution
| 1 | class Solution: |
| 2 | def compress(self, chars: List[str]) -> int: |
| 3 | write = 0 |
| 4 | i = 0 |
| 5 | |
| 6 | while i < len(chars): |
| 7 | char = chars[i] |
| 8 | count = 0 |
| 9 | |
| 10 | while i < len(chars) and chars[i] == char: |
| 11 | i += 1 |
| 12 | count += 1 |
| 13 | |
| 14 | chars[write] = char |
| 15 | write += 1 |
| 16 | |
| 17 | if count > 1: |
| 18 | for d in str(count): |
| 19 | chars[write] = d |
| 20 | write += 1 |
| 21 | |
| 22 | return write |
Step-by-Step Solution
Initialize Read and Write Pointers for Traversal and Compression
| 3 | write = 0 |
| 4 | i = 0 |
Objective
To set up two pointers: one for reading through the input array and one for writing compressed characters in-place.
Key Insight
Using two pointers allows simultaneous reading and writing without extra space. The read pointer scans the input to identify groups, while the write pointer tracks where to write compressed output. This separation prevents overwriting unprocessed characters and enables in-place modification.
Interview Quick-Check
Core Logic
The read pointer traverses the input array to identify groups, while the write pointer marks the position to write compressed characters.
State & Boundaries
Both pointers start at zero, ensuring the entire array is processed from the beginning.
Common Pitfalls & Bugs
Initializing pointers incorrectly or mixing their roles can cause data corruption or incorrect compression.
Traverse Input to Identify Consecutive Character Groups
| 6 | while i < len(chars): |
| 7 | char = chars[i] |
| 8 | count = 0 |
| 10 | while i < len(chars) and chars[i] == char: |
| 11 | i += 1 |
| 12 | count += 1 |
Objective
To iterate through the input array, counting the length of each group of identical characters.
Key Insight
By advancing the read pointer while the current character matches the group's character, the algorithm efficiently counts group length in a single pass. This counting is essential to determine whether to write just the character or the character plus count digits.
Interview Quick-Check
Core Logic
The inner loop increments the read pointer and count as long as characters match, identifying the full extent of each group.
State & Boundaries
The loop terminates when the read pointer reaches the array's end or encounters a different character.
Common Pitfalls & Bugs
Failing to check array bounds or incorrectly updating the read pointer can cause index errors or infinite loops.
Write Compressed Characters and Counts In-Place
| 14 | chars[write] = char |
| 15 | write += 1 |
| 17 | if count > 1: |
| 18 | for d in str(count): |
| 19 | chars[write] = d |
| 20 | write += 1 |
Objective
To write the compressed representation of each group into the array at the write pointer position.
Key Insight
Writing the character first ensures the compressed string starts correctly. If the count is greater than one, converting the count to a string and writing each digit individually preserves multi-digit counts. Incrementing the write pointer after each write maintains the correct position for subsequent writes.
Interview Quick-Check
Core Logic
Writing the character and then the count digits (if count > 1) in-place ensures the array reflects the compressed form without extra space.
State & Boundaries
The write pointer advances exactly by the number of characters written, maintaining correct indexing.
Common Pitfalls & Bugs
Not converting count to string or writing digits individually can cause incorrect compression for counts > 9.
Return Length of Compressed Array
| 22 | return write |
Objective
To return the final length of the compressed array after all groups have been processed.
Key Insight
The write pointer's position after processing all groups represents the length of the compressed array. Returning this value allows the caller to know the valid portion of the array.
Interview Quick-Check
Core Logic
Returning the write pointer value correctly indicates the length of the compressed array.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
while i < len(chars) and chars[i] == char:Start inner loop to count consecutive occurrences of the current character.
This loop advances the read pointer and increments count while the characters match, efficiently identifying group length.
chars[write] = charWrite the current character at the write pointer position.
Writing the character first ensures the compressed array starts with the correct character for the group.
chars[write] = dWrite each count digit at the write pointer position.
Writing digits individually maintains the correct order and placement of the count in the compressed array.
return writeReturn the length of the compressed array.
The write pointer's final position represents the length of the compressed array, signaling the valid portion of the array after compression.
write = 0Initialize the write pointer to track the position for writing compressed characters.
The write pointer marks where the next compressed character or count digit should be written, enabling in-place modification without overwriting unprocessed data.
if count > 1:Check if the count is greater than one to write count digits.
Only groups with more than one character require count digits to be written, preserving compression correctness.
for d in str(count):Iterate over each digit in the string representation of count.
Converting count to string and iterating digits handles multi-digit counts correctly, ensuring accurate compression.
i = 0Initialize the read pointer to traverse the input array.
The read pointer scans the input array to identify groups of consecutive characters, driving the compression process.
char = chars[i]Store the current character to identify the group.
Capturing the current character allows counting how many times it repeats consecutively, which is essential for compression.
i += 1Advance the read pointer to the next character.
Incrementing the read pointer moves the scan forward, enabling counting of the current group without missing characters.
count += 1Increment the count of the current character group.
Counting each occurrence is necessary to determine if the count should be written after the character.
write += 1Advance the write pointer after writing the character.
Incrementing the write pointer prepares the position for writing count digits or the next character.
write += 1Advance the write pointer after writing each count digit.
Incrementing the write pointer after each digit ensures subsequent digits or characters are written in the correct positions.
while i < len(chars):Start the outer loop to process the entire array.
This loop ensures every character in the array is visited and grouped appropriately until the end is reached.
count = 0Initialize the count of consecutive characters to zero.
Starting the count at zero prepares to tally the number of identical characters in the current group.
Test Your Understanding
Why must the write pointer only advance after fully processing each group of characters?
Because advancing the write pointer prematurely risks overwriting characters that have not yet been read, breaking the in-place compression logic and corrupting data.
Related Problems
Two Pointers pattern
Don't just read it. Drill it.
Reconstruct String Compression from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the String Compression drill