Log inSign up
mediumleetcodeNot Started

String Compression

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

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 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 O(1) extra space.

Example 1:

Input: chars = ["a","a","b","b","c","c","c"]
Output: 6, chars = ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

Example 2:

Input: chars = ["a"]
Output: 1, chars = ["a"]
Explanation: The only group is "a", which remains uncompressed since length is 1.

Example 3:

Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output: 4, chars = ["a","b","1","2"]
Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".

Constraints:

  • 1 <= chars.length <= 2000
  • chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Implement in-place array compaction using read and write pointers.
  • Convert multi-digit integer counts to character sequences.
  • Prove invariant safety (write <= read).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Modifying an array in-place based on consecutive duplicates.
  • Run-length compression with length returning.

Algorithmic Decision Tree:

  • Modifying an array in-place based on consecutive duplicates.
  • Run-length compression with length returning.

Connected Patterns:

Remove Duplicates from Sorted ArrayMove ZeroesString to Integer (atoi)

1. Auxiliary String Buffer

Intuition

Iterate through chars, counting contiguous runs. Append character and count (if > 1) to a temporary string or list. Copy the characters back into chars and return the new length.

When to apply: Basic conceptual implementation.

Algorithm

  1. Initialize res = [].
  2. Loop i from 0 to n - 1:
  3. char = chars[i], count = 0.
  4. While i < n && chars[i] == char: count++, i++.
  5. res.push(char).
  6. If count > 1: push each digit of count to res.
  7. Copy res into chars.
  8. Return res.length.

Auxiliary String Buffer

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, a, b, b, c, c, c]
Current operationSTEP 1 OF 6
Observation: First run consists of 'a' from index 0 to 1 (length 2)
Visual state
Values and pointers at this exact step
array
S
a
a
b
b
c
c
c
0
↑ GROUP 'a'
1
↑ COUNT = 2
2
3
4
5
6
Variables at this step
groupChar
a
count
2
buffer
a2
Check / comparison
Group 1: 'a' appears 2 consecutive times.
Decision / next transition
Append char 'a' and count '2' to auxiliary buffer: 'a2'.
Why this step matters

Observation: First run consists of 'a' from index 0 to 1 (length 2).

Decision: Append character 'a' followed by count string '2' to auxiliary string buffer: buffer = 'a2'.

Invariant: Runs of length > 1 append their decimal digit count.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5class Solution {
6public:
7 int compress(std::vector<char>& chars) {
8 std::vector<char> res;
9 int n = chars.size(), i = 0;
10 while (i < n) {
11 char c = chars[i];
12 int count = 0;
13 while (i < n && chars[i] == c) {
14 count++;
15 i++;
16 }
17 res.push_back(c);
18 if (count > 1) {
19 for (char digit : std::to_string(count)) {
20 res.push_back(digit);
21 }
22 }
23 }
24 for (size_t k = 0; k < res.size(); ++k) {
25 chars[k] = res[k];
26 }
27 return res.size();
28 }
29};
30
31int main() {
32 Solution sol;
33 std::vector<char> chars = {'a','a','b','b','c','c','c'};
34 int len = sol.compress(chars);
35 std::cout << len << std::endl; // 6
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N) — Allocates an auxiliary array of size up to N.
  • Space complexity: O(N)

Why Brute Force Doesn't Scale:

In-place write pointer eliminates intermediate array allocation.

Strict O(1) space complexity.

2. Lookahead Two Pointers (In-Place Loop)

Intuition

Maintain anchor (start of current run) and write = 0. Iterate read from 0 to N - 1. If read == N - 1 || chars[read + 1] != chars[read], a group ends. Write chars[anchor] to chars[write++]. If read >= anchor + 1, write the string representation of read - anchor + 1. Set anchor = read + 1.

When to apply: When structuring the loop around anchor indices.

Algorithm

  1. Initialize anchor = 0, write = 0, n = chars.length.
  2. For read from 0 to n - 1:
  3. If read == n - 1 || chars[read + 1] != chars[read]:
  4. chars[write++] = chars[anchor]
  5. If read > anchor:
  6. For d in String(read - anchor + 1): chars[write++] = d.
  7. anchor = read + 1.
  8. Return write.

Lookahead Two Pointers (In-Place Loop)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, a, b, b, c, c, c]
Current operationSTEP 1 OF 6
Observation: Write pointer $w = 0$
Visual state
Values and pointers at this exact step
array
S
a
a
b
b
c
c
c
0
↑ w=0 (WRITE)
1
↑ r=1 (LOOKAHEAD)
2
3
4
5
6
Variables at this step
w
2
r
2
group
a
count
2
Check / comparison
Lookahead finds group 'a' ends at idx 1. Run length = 2.
Decision / next transition
chars[w++] = 'a'. Since count > 1, chars[w++] = '2'. w is now 2.
Why this step matters

Observation: Write pointer w = 0. Read pointer expands through consecutive 'a's (length 2).

Decision: Write character: chars[0] = 'a'. Write count: chars[1] = '2'. Advance w = 2.

Invariant: w <= r always holds because compressed representations never exceed original run lengths.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5class Solution {
6public:
7 int compress(std::vector<char>& chars) {
8 int anchor = 0, write = 0, n = chars.size();
9 for (int read = 0; read < n; ++read) {
10 if (read == n - 1 || chars[read + 1] != chars[read]) {
11 chars[write++] = chars[anchor];
12 if (read > anchor) {
13 for (char c : std::to_string(read - anchor + 1)) {
14 chars[write++] = c;
15 }
16 }
17 anchor = read + 1;
18 }
19 }
20 return write;
21 }
22};
23
24int main() {
25 Solution sol;
26 std::vector<char> chars = {'a','a','b','b','c','c','c'};
27 std::cout << sol.compress(chars) << std::endl; // 6
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N) — Single pass over chars array with constant extra space.
  • Space complexity: O(1)

3. Two Pointers While-Loop Compaction (Optimal)

Intuition

Maintain write = 0 and read = 0. For each group starting at read, advance readEnd while readEnd < n && chars[readEnd] == chars[read]. Write chars[read] at chars[write++]. Calculate count = readEnd - read. If count > 1, convert count to its decimal digits and write each to chars[write++]. Update read = readEnd.

When to apply: The standard gold standard solution for clean, robust in-place run-length encoding.

Algorithm

  1. Initialize write = 0, read = 0, n = chars.length.
  2. While read < n:
  3. readEnd = read.
  4. While readEnd < n && chars[readEnd] == chars[read]: readEnd++.
  5. chars[write++] = chars[read].
  6. count = readEnd - read.
  7. If count > 1:
  8. For digit in to_string(count): chars[write++] = digit.
  9. read = readEnd.
  10. Return write.

In-Place Read-Write Two-Pointer Array Compression

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, a, b, b, c, c, c]
Current operationSTEP 1 OF 6
Observation: Read group of 'a' from index 0 to 1 (run length 2)
Visual state
Values and pointers at this exact step
array
S
a
a
b
b
c
c
c
0
↑ write=0
1
↑ read=1 (run of 'a')
2
3
4
5
6
Variables at this step
currentChar
a
runLength
2
writeIdx
0
readIdx
1
Why this step matters

Observation: Read group of 'a' from index 0 to 1 (run length 2).

Decision: Write character 'a' at chars[write++]. Write digit '2' at chars[write++].

Invariant: write pointer is always <= read pointer, preventing data overwrite.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5class Solution {
6public:
7 int compress(std::vector<char>& chars) {
8 int n = chars.size();
9 int write = 0, read = 0;
10
11 while (read < n) {
12 int readEnd = read;
13 while (readEnd < n && chars[readEnd] == chars[read]) {
14 readEnd++;
15 }
16
17 chars[write++] = chars[read];
18 int count = readEnd - read;
19
20 if (count > 1) {
21 for (char c : std::to_string(count)) {
22 chars[write++] = c;
23 }
24 }
25 read = readEnd;
26 }
27
28 return write;
29 }
30};
31
32int main() {
33 Solution sol;
34 std::vector<char> chars = {'a','a','b','b','c','c','c'};
35 std::cout << sol.compress(chars) << std::endl; // 6
36 std::vector<char> chars2 = {'a','b','b','b','b','b','b','b','b','b','b','b','b'};
37 std::cout << sol.compress(chars2) << std::endl; // 4
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N) — Every character in chars is visited at most twice; uses O(1) memory variables.
  • Space complexity: O(1) extra space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Auxiliary String AccumulatorO(N)O(N)Easy to write using extra memory.Violates O(1) space constraint.
2.Two Pointers In-Place Read/Write (Optimal)OptimalO(N)O(1) auxiliary spaceSingle forward pass, zero extra allocations, strictly optimal.None.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Writing digit 1 when character group length is 1.

Pitfall 2:

Writing multi-digit counts as a single character or string object instead of individual character digits.

Crucial Edge Cases to Validate:

  • All distinct single characters (chars = [a,b,c]): count=1 for each group, no counts are written, returns original length 3.
  • Count >= 10 (e.g. 12 bs): Digits 1 and 2 are written to separate consecutive character slots.
  • Single character array (chars = [a]): Returns 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the invariant write <= read to explain why in-place modification is mathematically safe.
  2. Show how multi-digit counts are converted into individual digit characters.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is it guaranteed that the write pointer will never overwrite unread characters in the chars array?

Back to DSA Sheet