Skip to main content

443. String Compression

medium

Run-length-encode a character array in place: replace each maximal run with the character followed by its count (only for runs > 1). The space constraint is what makes this medium, not easy.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array of characters chars, compress it in place. The length after compression must always be smaller than or equal to the original array. Replace each group of consecutive repeating characters with the character followed by the group's length. If the group's length is 1, no number is appended. Lengths longer than one digit must be split across multiple cells (e.g., a run of 12 becomes ['1','2']). After you're done, return the new length and modify the array in place.

Constraints

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

Examples

Example 1

Input
chars = ["a","a","b","b","c","c","c"]
Output
Return 6, chars = ["a","2","b","2","c","3"]

Example 2

Input
chars = ["a"]
Output
Return 1, chars = ["a"]

Explanation: Single characters are written without a count.

Example 3

Input
chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output
Return 4, chars = ["a","b","1","2"]

Explanation: The run of 12 'b's becomes 'b','1','2'.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Two indices: read and write. Read scans through groups; write places the compressed output back into the same array.

Hint 2

For each group, write the character once. If the group length is > 1, write each digit of the length (left to right) one cell at a time.

Hint 3

Be careful with multi-digit counts — a count of 12 occupies two cells, not one.

Solution approach

Reveal approach

Two-pointer compression in the same buffer. read = 0, write = 0. Loop while read < n: let groupStart = read; advance read while read < n and chars[read] == chars[groupStart] — now read - groupStart is the count. Write chars[groupStart] into chars[write++]. If count > 1, convert count to a decimal string and copy each digit char into chars[write++] in order. After the outer loop, return write. O(n) time, O(1) extra space (the int-to-string conversion of count uses up to 4 chars on the stack).

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • two-pointers
  • string-matching

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Meta
  • Amazon
  • Microsoft

Practice these live with InterviewChamp.AI

Drill String Compression and Strings problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →