MediumTwo PointersStringUpdated Sep 2026

443. String Compression

Asked at Salesforce, Goldman Sachs, Anduril, Pinterest

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Two Pointers

Companies

4

Problem

You are given an array of characters chars. Compress it in place using this rule: look at each group of consecutive equal characters. If a group has only one character, write just that character. If a group has more than one character, write the character followed by the group's size as digits.

Do not return a new string. Instead, overwrite the front of the input array chars with the compressed result, and return the new length. Anything in the array past that length is ignored.

Counts of 10 or more take several positions. For example, a group of 12 identical characters becomes the character plus "1" and "2". You must use only constant extra space, so you cannot build a separate output array.

Groups become character plus count

charsaabbcccaabbccc0123456Read the array as groups of equal charactersresulta2b2c3012345Each group writes its character, then its count as digits
Three groups of repeated characters turn into a2b2c3, and the new length is 6.

Constraints

  • ●1 <= chars.length <= 2000
  • ●chars[i] is a lowercase English letter, an uppercase English letter, a digit, or a symbol
  • ●The algorithm must use O(1) extra space

Examples

Example 1
Inputchars = ["a","a","b","b","c","c","c"]
Output6
WhyThe groups are "aa", "bb" and "ccc". Each group has more than one character, so we write the character and its count: a2b2c3. That is 6 characters, so we return 6.
Example 2
Inputchars = ["a"]
Output1
WhyThere is one group of size 1. A single character is written as itself, with no count. The array stays ["a"] and the length is 1.
Example 3
Inputchars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output4
WhyThe groups are "a" (size 1) and twelve "b"s. The first group becomes just "a". The second becomes "b" plus the digits "1" and "2", because 12 is written one digit per position. The result is ab12, length 4.

Asked At

4 companies
CompanyDifficulty
SalesforceMediumView all Salesforce questions →
Goldman SachsMediumView all Goldman Sachs questions →
AndurilMediumView all Anduril questions →
PinterestMediumView all Pinterest questions →

How to Think About It

1

Brute force: build a new string by scanning and counting consecutive characters.

2

Two pointers approach: use a read pointer to scan and a write pointer to compress in-place.

3

For each group, write the character, then write the count as individual digits if count > 1.

4

Handle multi-digit counts (e.g., 12 becomes characters "1" and "2").

5

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.

Read pointer and write pointer

charsaabbccc0123456readwriteStart: both pointers sit at index 0charsa2bbccc0123456readwriteGroup "aa" is done: write a and 2, then move read to thenext groupcharsa2b2c3012345All groups written; write pointer equals the new length 6count > 1 → write each digit of countcount == 1 → write the character onlyreturn write
The read pointer finds the end of each group; the write pointer places the character and the count digits.
ComplexityTime O(n)Space O(1)The read pointer touches each character once, and the write pointer only moves forward, so the whole scan is linear and no extra array is used.

What Trips People Up in Real Interviews

1

Clarify the compression format: only append count when count >= 2.

2

For counts >= 10, write each digit separately (not the number itself).

3

The compressed array must be modified in-place using the original array.

4

Edge case: a single character group with count 1 writes only the character.

5

Return the new length, not the compressed string itself.

Solution Code

O(n) time
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 write

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask String Compression?

String Compression is asked at Salesforce, Goldman Sachs, Anduril, Pinterest. 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.