#443

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

String Compression

Compress a character array in-place by converting consecutive repeated characters into counts using two-pointer scanning.

two pointers string

Problem Statement

Given an array of characters chars, compress it using the following approach: identify groups of consecutive repeating characters and replace each group with the character followed by its count if the count is greater than one.

The compression must be done in-place in the original array chars, and counts of 10 or more must be split into separate digits stored in consecutive indices. Return the new length of the array after compression while modifying the first part of chars accordingly.

Examples

Example 1

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

Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

Example 2

Input: chars = ["a"]

Output: Return 1, and the first character of the input array should be: ["a"]

The only group is "a", which remains uncompressed since it's a single character.

Example 3

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

Output: Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

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.

Solution Approach

Use Two Pointers to Track Groups

Initialize a read pointer to iterate through the array and a write pointer to overwrite chars in-place. For each group of consecutive identical characters, increment the read pointer until the group ends, then write the character at the write pointer.

Write Counts as Separate Characters

If a group length is greater than one, convert the count to a string and write each digit into the array using the write pointer. This ensures counts like 12 become ['1','2'] in the array, matching the in-place requirement.

Update Pointers Correctly

After writing a character and its count, move the write pointer forward appropriately. Continue until the read pointer reaches the end, ensuring that every group is processed and the array reflects the compressed string with minimal space overhead.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because each character is read and written at most once. Space complexity is O(1) as all operations are performed in-place without using extra arrays.

What Interviewers Usually Probe

Are you using a read and write pointer to compress without extra space?
How do you handle counts that are larger than 9 when writing them back?
Can you guarantee that your method overwrites the array correctly and maintains proper length?

Common Pitfalls or Variants

Common pitfalls

Forgetting to split counts larger than 9 into separate digits.
Overwriting characters before processing all in a group, causing incorrect compression.
Using extra space instead of modifying the array in-place, violating problem constraints.

Follow-up variants

Compress strings where only certain characters need counting, e.g., vowels.
Allow compression using a delimiter instead of counts, changing in-place logic slightly.
Handle arrays with non-alphabetic symbols while maintaining the same two-pointer scanning approach.

FAQ

What pattern does String Compression 443 use?

It uses a two-pointer scanning with invariant tracking pattern, identifying groups of repeated characters in-place.

How do I handle counts greater than 9?

Convert the count to a string and write each digit separately into the array to maintain in-place compression.

Is extra space allowed for this problem?

No, all compression must be done in the original array, so space complexity must remain O(1).

Can single characters remain uncompressed?

Yes, groups of length one are written as-is without a count following the character.

What common mistakes should I avoid?

Do not overwrite unread characters, forget to split large counts, or use extra space outside the array.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def compress(self, chars: List[str]) -> int:
        i, k, n = 0, 0, len(chars)
        while i < n:
            j = i + 1
            while j < n and chars[j] == chars[i]:
                j += 1
            chars[k] = chars[i]
            k += 1
            if j - i > 1:
                cnt = str(j - i)
                for c in cnt:
                    chars[k] = c
                    k += 1
            i = j
        return k

Continue Practicing

#481 magical string #392 is subsequence #522 longest uncommon subsequence ii