What is the time complexity of String Compression?

The optimal solution has a time complexity of O(n).

What data structures are used to solve String Compression?

This problem uses Two Pointers, String. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving String Compression?

Insight 1: The core idea is to use two pointers: one to read the input array and another to write the compressed characters to the same array. Insight 2: We need to iterate through the array, counting consecutive repeating characters. Once the repeating sequence ends, we write the character and its count (if greater than 1) to the array.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

String Compression - LeetCode 443 Solution

Q: Which companies ask LeetCode 443. String Compression in interviews?

This problem is frequently asked at Affirm, CrowdStrike, EPAM Systems, Expedia, Goldman Sachs and 14 more companies.

String Compression - Complete Solution Guide

String Compression is LeetCode problem 443, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given an array of characters chars , compress it using the following algorithm: Begin with an empty string s . For each group of consecutive repeating characters in chars : If the group's length is 1 , append the character to s . Otherwise, append the character followed by the group's length. The compressed string s should not be returned separately , but instead, be stored in the input character array chars . Note that group lengths that are 10 or longer will be split into multiple characters i

Detailed Explanation

The problem requires compressing a given array of characters `chars` in-place. Compression is achieved by replacing consecutive repeating characters with the character followed by the count of repetitions. If a character appears only once, it remains as is. The counts, if greater than 1, are appended to the array as individual characters. For example, 'aabbbccc' becomes 'a2b3c3'. The function should modify the input array directly and return the new length of the compressed array.

Solution Approach

The solution uses a two-pointer approach. `read_ptr` iterates through the input `chars` array, and `write_ptr` writes the compressed output to the same array, starting from index 0. The algorithm maintains a `count` of consecutive repeating characters. When a different character is encountered or the end of the array is reached, the current character and its count (if greater than 1) are written to the `chars` array using the `write_ptr`.

Step-by-Step Algorithm

Step 1: Initialize `read_ptr` and `write_ptr` to 0, and `n` to the length of `chars`.
Step 2: Iterate through the `chars` array using the `read_ptr`.
Step 3: For each character, count the number of consecutive repeating characters using an inner loop.
Step 4: Write the current character to the `chars` array at the `write_ptr` index, and increment `write_ptr`.
Step 5: If the count of repeating characters is greater than 1, convert the count to a string. Iterate through this string, writing each digit character to the `chars` array at the `write_ptr` index, and increment `write_ptr` after each write.
Step 6: Move the `read_ptr` to the next distinct character. Repeat steps 3-5 until `read_ptr` reaches the end of the array.
Step 7: Return the `write_ptr`, which represents the new length of the compressed array.

Key Insights

Insight 1: The core idea is to use two pointers: one to read the input array and another to write the compressed characters to the same array.
Insight 2: We need to iterate through the array, counting consecutive repeating characters. Once the repeating sequence ends, we write the character and its count (if greater than 1) to the array.
Insight 3: Numbers greater than 9 need to be split into individual digits and written as separate characters into the compressed array. This is a critical implementation detail.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Two Pointers, String.

Companies

Asked at: Affirm, CrowdStrike, EPAM Systems, Expedia, Goldman Sachs, IBM, Lyft, Palo Alto Networks, Paytm, PhonePe, Pinterest, Ripple, Rivian, Salesforce, ServiceNow, Snap, Yandex, Yelp, Zoox.

String Compression | LeetCode 443

Medium

Two Pointers String

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int compress(char[] chars) {
        int read_ptr = 0;
        int write_ptr = 0;
        int n = chars.length;

        while (read_ptr < n) {
            char current_char = chars[read_ptr];
            int count = 0;
            
            // Count consecutive repeating characters
            while (read_ptr < n && chars[read_ptr] == current_char) {
                read_ptr++;
                count++;
            }
            
            // Write the character
            chars[write_ptr] = current_char;
            write_ptr++;
            
            // Write the count if it's greater than 1
            if (count > 1) {
                for (char digit : String.valueOf(count).toCharArray()) {
                    chars[write_ptr] = digit;
                    write_ptr++;
                }
            }
        }
        
        return write_ptr;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 443: String Compression - Detailed explanation and solution approaches.

Topics

Two Pointers String

Companies

AffirmCrowdStrikeEPAM SystemsExpediaGoldman SachsIBMLyftPalo Alto Networks

Stats

Difficulty:Medium

Languages:4

Companies:19

Problem #:443

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Initialize `read_ptr` and `write_ptr` to 0, and `n` to the length of `chars`.
2
Step 2: Iterate through the `chars` array using the `read_ptr`.
3
Step 3: For each character, count the number of consecutive repeating characters using an inner loop.
4
Step 4: Write the current character to the `chars` array at the `write_ptr` index, and increment `write_ptr`.
5
Step 5: If the count of repeating characters is greater than 1, convert the count to a string. Iterate through this string, writing each digit character to the `chars` array at the `write_ptr` index, and increment `write_ptr` after each write.
6
Step 6: Move the `read_ptr` to the next distinct character. Repeat steps 3-5 until `read_ptr` reaches the end of the array.
7
Step 7: Return the `write_ptr`, which represents the new length of the compressed array.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The outer loop iterates through the array. The inner loop counts consecutive repeating characters, and the string conversion for counts takes at most O(log n) time. Because the operations are done in place and the extra space is constant, the space complexity is O(1).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using a temporary string

An alternative approach is to create a temporary string and build the compressed string in it. Then, copy the contents of the string back to the `chars` array.

Time: O(n)Space: O(n)

Trade-offs: This approach uses O(n) extra space, making it less efficient in terms of space complexity compared to the in-place solution. The in-place solution is generally preferred due to the problem constraint of constant extra space.

✨

Key Insights

1Insight 1: The core idea is to use two pointers: one to read the input array and another to write the compressed characters to the same array.
2Insight 2: We need to iterate through the array, counting consecutive repeating characters. Once the repeating sequence ends, we write the character and its count (if greater than 1) to the array.
3Insight 3: Numbers greater than 9 need to be split into individual digits and written as separate characters into the compressed array. This is a critical implementation detail.

📚

Key Terms Explained

For Students

Two Pointers

Using two indices to traverse data from different positions simultaneously.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Input array with only one character (e.g., ['a']). The solution correctly returns 1, leaving the array unchanged.
Edge case 2: Input array with all identical characters (e.g., ['a', 'a', 'a', ..., 'a']). The solution handles the count correctly, converting it to a string and appending it to the array (e.g., ['a', '1', '0', '0']).
Edge case 3: Input array with no repeating characters (e.g., ['a', 'b', 'c']). The solution simply copies the array without any compression, resulting in the same length.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to handle the case where the count is greater than 9. The digits of the count need to be treated as individual characters.

✗Common mistake 2: Incorrectly updating the `write_ptr` after writing the count. Each digit of the count needs to increment the `write_ptr`.

✗Common mistake 3: Not considering the case where a character appears only once. The count should not be written in this case.

✗Common mistake 4: Failing to reset the count when a new character is encountered.

✗Common mistake 5: Not returning the correct length of the compressed array (which is the final value of `write_ptr`).

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data compression techniques used in file archiving (e.g., ZIP, GZIP) employ similar strategies to reduce file sizes by identifying and representing repeating sequences of data more efficiently.

🏦Real-world scenario 2: Run-length encoding (RLE) is a specific compression algorithm based on this principle, used in image and video compression. Especially useful for simple images or videos with large areas of the same color.

🎮Real-world scenario 3: Compressing log files where repetitive entries occur frequently, saving storage space.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

The two-pointer technique is powerful for sorted arrays. The key insight is recognizing when elements can be processed from both ends simultaneously.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

The most common mistake is not handling the case when pointers meet. Always consider the termination condition.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 23, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 14

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 7

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jun 30

❓

Frequently Asked Questions

How do I avoid infinite loops with two pointers?

Always ensure your loop condition guarantees termination (typically left < right or slow != fast). Move at least one pointer in each iteration, and handle edge cases where pointers might not move (like skipping duplicates). Draw out pointer movement on paper first.

What is the sliding window technique for string problems?

Sliding window maintains a "window" of characters with two pointers. Expand the right pointer to include characters, shrink from left when window violates constraints. Useful for substring problems, anagrams, and longest/shortest substring with properties.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "String Compression"?

For this medium-level Two Pointers problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?