String Compression - Practice Coding Problems

String Compression - Problem

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: Group lengths that are 10 or longer will be split into multiple characters in chars.

After you are done modifying the input array, return the new length of the array.

You must write an algorithm that uses only constant extra space.

Input & Output

Example 1 — Basic Compression

$ Input: chars = ["a","a","b","b","c","c","c"]

› Output: 6

💡 Note: Groups: 'a' appears 2 times, 'b' appears 2 times, 'c' appears 3 times. Compressed: ['a','2','b','2','c','3']. Length is 6.

Example 2 — Single Characters

$ Input: chars = ["a"]

› Output: 1

💡 Note: Single character 'a' with count 1, so no count is appended. Result: ['a']. Length is 1.

Example 3 — Mixed Groups

$ Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]

› Output: 4

💡 Note: 'a' appears 1 time (no count), 'b' appears 12 times. Compressed: ['a','b','1','2']. Length is 4.

Constraints

1 ≤ chars.length ≤ 2000
chars[i] is a lowercase English letter, uppercase English letter, or digit

Visualization

Tap to expand

Understanding the Visualization

Input

Array of characters with consecutive duplicates

Process

Count consecutive groups and compress

Output

Return new length of compressed array

Key Takeaway

🎯 Key Insight: Compressed form is never longer than original, so we can modify in-place

Asked in

M Microsoft 35 a Amazon 28 G Google 22 🍎 Apple 18

The key insight is that we can compress the array in-place using two pointers since the compressed form is never longer than the original. The optimal approach uses a read pointer to count consecutive characters and a write pointer to store the compressed result. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers In-Place	O(n)	O(1)	Use read pointer to scan input and write pointer to build compressed output in same array
Brute Force with Extra Space	O(n)	O(n)	Build compressed string separately then copy back to input array

Two Pointers In-Place — Algorithm Steps

Initialize read and write pointers
Read pointer counts consecutive characters
Write pointer stores character and count
Continue until all characters processed

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan & Count

Read pointer scans and counts consecutive characters

Write Compressed

Write pointer places character and count at correct position

Continue

Process continues until all characters handled

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* chars, int charsSize) {
    if (charsSize == 0) return 0;
    
    int write = 0;
    int read = 0;
    
    while (read < charsSize) {
        char ch = chars[read];
        int count = 1;
        
        // Count consecutive characters
        while (read + 1 < charsSize && chars[read + 1] == ch) {
            count++;
            read++;
        }
        
        // Write character
        chars[write] = ch;
        write++;
        
        // Write count if > 1
        if (count > 1) {
            char countStr[20];
            sprintf(countStr, "%d", count);
            for (int i = 0; countStr[i]; i++) {
                chars[write] = countStr[i];
                write++;
            }
        }
        
        read++;
    }
    
    return write;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for character array
    char chars[1000];
    int charsSize = 0;
    
    for (int i = 0; line[i]; i++) {
        if (line[i] >= 'a' && line[i] <= 'z' || line[i] >= 'A' && line[i] <= 'Z') {
            chars[charsSize++] = line[i];
        }
    }
    
    int result = solution(chars, charsSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array with read pointer, constant work per character

✓ Linear Growth

Space Complexity

O(1)

Only uses two pointer variables, modifies input array in-place

✓ Linear Space

68.0K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers In-Place — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler