String Compression

String Compression is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the In-place Array Modification subpattern.

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 constant extra space.

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"] Explanation: 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"] Explanation: 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"]. 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.

Topics and companies

Topics: Two Pointers, String.

Reported in interviews at Goldman Sachs, Yandex, Microsoft, Apple, Citrix, Facebook, Amazon, eBay, Redfin, Google, VMware, Cisco and others.

How to practise String Compression on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N), where N is the length of chars. Each character is read and written at most once. time and O(1), only a few integer variables and a small string (for group length) are used. No extra space proportional to input size. space.

Open String Compression in the code editor, or read the String Compression editorial for a worked solution with its approach and complexity analysis.

Where String Compression sits in the DSA pattern sheet

Problems related to String Compression

Other problems that use the same In-place Array Modification and Two Pointers techniques:

Preparing this workspace.