String Compression is a classic array manipulation problem from LeetCode75 that tests your understanding of two-pointer traversal, in-place operations, and character grouping logic. While the task might sound simple compressing repeated characters doing it efficiently and in-place without using extra memory adds an interesting twist.
In this blog post, we’ll take you through the String Compression in Python problem step by step, explain the logic behind the code and help you master one of the essential LeetCode 75 challenges.
Table of Contents
Problem Statement
Given an array of characters
chars, compress it in-place.
The length after compression must be returned, and the first part of the arraycharsshould contain the compressed string.
What does compression mean?
- Replace groups of the same character with the character followed by its count.
- Single characters remain unchanged.
- You must not return a new array—do it using the original input array.
Examples
Input: ["a","a","b","b","c","c","c"]
Output: ["a","2","b","2","c","3"]
Return: 6
Input: ["a"]
Output: ["a"]
Return: 1
Python Solution – Step-by-Step Explanation
Let’s look at the code and walk through what it does:
class Solution:
def compress(self, chars: List[str]) -> int:
i = 0
res = 0
while i < len(chars):
group_length = 1
while (i + group_length < len(chars)
and chars[i + group_length] == chars[i]):
group_length += 1
chars[res] = chars[i]
res += 1
if group_length > 1:
str_repr = str(group_length)
chars[res:res+len(str_repr)] = list(str_repr)
res += len(str_repr)
i += group_length
return res
Step 1: Initialize Pointers
i = 0
res = 0
iis used to scan through the input.reskeeps track of where to write the compressed result in the same array.
Step 2: Count Consecutive Characters
group_length = 1
while i + group_length < len(chars) and chars[i + group_length] == chars[i]:
group_length += 1
This inner loop counts how many times the current character repeats. We’ll use this number to determine whether we need to compress.
Step 3: Write the Character
chars[res] = chars[i]
res += 1
We always write the current character to the res index of the array. This is mandatory—whether it’s compressed or not.
Step 4: Write the Count (If More Than 1)
if group_length > 1:
str_repr = str(group_length)
chars[res:res+len(str_repr)] = list(str_repr)
res += len(str_repr)
- If a character repeats, we convert its count to string (e.g., 12 → “1”, “2”) and place those characters right after the letter.
Step 5: Move to the Next Group
i += group_length
Jump forward by the size of the group to start checking the next unique character.
Step 6: Return Compressed Length
return res
Return the length of the compressed list. Only the first res characters in chars are valid.
Why This Solution Works
This method:
- Avoids extra memory by modifying the input array directly.
- Keeps track of the write position using
res. - Handles both single and multiple occurrences efficiently.
- Uses O(n) time and O(1) space.
Edge Cases to Consider
| Case | Output |
|---|---|
| [“a”] | [“a”], return 1 |
| [“a”, “a”, “a”, “a”, “a”, “a”] | [“a”, “6”], return 2 |
| [“a”, “b”, “c”] | [“a”, “b”, “c”], 3 |
| [“a”, “a”, “b”, “b”, “c”] | [“a”, “2”, “b”, “2”, “c”], 5 |
Real-World Relevance
- Used in data compression techniques
- Demonstrates skills in in-place modification and memory efficiency
- A common pattern in interview scenarios where optimizing memory is critical
Conclusion
The String Compression in Python problem is a must-practice for anyone preparing for coding interviews or working on algorithmic problem-solving. It sharpens your skills in in-place array manipulation, two-pointer techniques and group-based data handling—all without using extra memory.
By mastering this problem, you not only gain confidence in handling character arrays but also build a solid foundation for tackling real-world challenges like text compression, data stream processing, efficient storage and custom encoding schemes. It’s a great example of how optimizing space and logic can lead to cleaner, more scalable code making it essential for every developer’s toolkit.
Related Read
💡 https://vanitaai.com/increasing-triplet-subsequence/
Stay tuned on Vanita.ai for more deep dives into essential LeetCode 75 problems and practical interview prep content.