String Compression
Asked at Salesforce
Problem
Given a character array chars, compress it in-place using the following rule: groups of consecutive identical characters are replaced by the character followed by the count of repetitions. The count is only written if greater than 1. Return the new length of the compressed array.
Asked At
| Company | Difficulty | |
|---|---|---|
| Salesforce | MEDIUM | View all Salesforce questions → |
How to Think About It
Brute force: build a new string by scanning and counting consecutive characters.
Two pointers approach: use a read pointer to scan and a write pointer to compress in-place.
For each group, write the character, then write the count as individual digits if count > 1.
Handle multi-digit counts (e.g., 12 becomes characters "1" and "2").
Optimal: use two pointers with O(1) extra space, writing compressed characters as you scan.
Optimal Approach
Use two pointers: a read pointer i scans through the array, while a write pointer j marks where to write. For each group of identical characters starting at i, count the length of the group. Write the character at position j, then write the count digits if count > 1. Advance i past the group and continue. The write pointer j at the end gives the compressed length. For multi-digit counts like 12, write "1" then "2" at consecutive positions.
What Trips People Up in Real Interviews
Clarify the compression format: only append count when count >= 2.
For counts >= 10, write each digit separately (not the number itself).
The compressed array must be modified in-place using the original array.
Edge case: a single character group with count 1 writes only the character.
Return the new length, not the compressed string itself.
Solution Code
def compress(chars):
write = 0
read = 0
n = len(chars)
while read < n:
char = chars[read]
count = 0
while read < n and chars[read] == char:
read += 1
count += 1
chars[write] = char
write += 1
if count > 1:
for digit in str(count):
chars[write] = digit
write += 1
return writeFrequently Asked Questions
What is the String Compression problem?
Given a character array chars, compress it in-place using the following rule: groups of consecutive identical characters are replaced by the character followed by the count of repetitions. The count is only written if greater than 1. Return the new length of the compressed array.
How do you solve String Compression?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask String Compression?
String Compression is asked at Salesforce. It is a medium difficulty problem.
What are common mistakes on String Compression?
- Clarify the compression format: only append count when count >= 2.
- For counts >= 10, write each digit separately (not the number itself).
- The compressed array must be modified in-place using the original array.
- Edge case: a single character group with count 1 writes only the character.
- Return the new length, not the compressed string itself.