String Compression solution in Python

Problem Description

Ah, the classic “String Compression” problem! It’s like trying to fit your entire wardrobe into a single suitcase for a weekend trip. You know you have too many clothes, but do you really want to leave that favorite shirt behind? In this LeetCode challenge, you’re tasked with compressing a list of characters in such a way that consecutive duplicates are replaced by a single character followed by the count of those duplicates.

For example, if you have the string ["a","a","b","b","c","c","c"], you should transform it into ["a","2","b","2","c","3"]. Easy, right? Just like deciding which shoes to leave behind!

Code Solution


class Solution:
    def compress(self, chars: list[str]) -> int:
        ans = 0
        i = 0

        while i < len(chars):
            letter = chars[i]
            count = 0
            while i < len(chars) and chars[i] == letter:
                count += 1
                i += 1
            chars[ans] = letter
            ans += 1
            if count > 1:
                for c in str(count):
                    chars[ans] = c
                    ans += 1

        return ans

Approach

The approach here is straightforward: we iterate through the list of characters, counting how many times each character appears consecutively. When we encounter a new character, we store the previous character and its count in the list. If the count is greater than one, we also append the count as a string. This way, we effectively compress the string in-place.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the length of the input list. We traverse the list once.
Space Complexity	O(1), since we are modifying the input list in place and using a constant amount of extra space.

Real-World Example

Imagine you’re at a concert, and you see a group of fans wearing the same T-shirt. Instead of counting each fan individually, you just shout, “Hey, there are 10 of you wearing the same shirt!” That’s essentially what this algorithm does—counts duplicates and summarizes them in a more compact form.