String Compression

Med

#0430Time: O(N), where N is the length of `chars`. The first pass to build the string takes O(N) time. The second pass to copy the result back into the array also takes O(N) time. Thus, the total time complexity is O(N).Space: O(N). The `StringBuilder` can grow up to a size proportional to N. For an input like `['a', 'b', 'c', 'd']`, the compressed string is the same, requiring O(N) extra space. This violates the problem's constraint.19 companies

Patterns

Two Pointers

Data structures

String

Companies

EPAM Systems Expedia Goldman Sachs IBM

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward way to solve this is to build the compressed string in an auxiliary data structure, like a StringBuilder, and then copy the result back into the input array. This approach is intuitive and easy to implement but fails the crucial constant extra space constraint of the problem.

Algorithm

Initialize an empty StringBuilder.
Iterate through the input chars array using a pointer i.
For each character at chars[i], find the end of the consecutive group and determine its count.
Append the character to the StringBuilder.
If count is greater than 1, append the string representation of count to the StringBuilder.
Advance i to the start of the next group.
After the loop, copy the characters from the StringBuilder back to the chars array.
Return the length of the StringBuilder.

Walkthrough

This method involves two main phases. First, we iterate through the input character array to identify groups of consecutive characters. For each group, we append the character followed by its count (if the count is greater than 1) to a StringBuilder. This effectively builds the compressed string in memory. In the second phase, we overwrite the original chars array with the content of the StringBuilder. The final length of the compressed string is simply the length of the StringBuilder.

1public int compress(char[] chars) {2    if (chars == null || chars.length == 0) {3        return 0;4    }5    StringBuilder sb = new StringBuilder();6    int i = 0;7    while (i < chars.length) {8        char currentChar = chars[i];9        int count = 0;10        int j = i;11        while (j < chars.length && chars[j] == currentChar) {12            j++;13            count++;14        }15        sb.append(currentChar);16        if (count > 1) {17            sb.append(count);18        }19        i = j;20    }21    22    char[] compressedChars = sb.toString().toCharArray();23    for (int k = 0; k < compressedChars.length; k++) {24        chars[k] = compressedChars[k];25    }26    27    return sb.length();28}

Complexity

Time

O(N), where N is the length of `chars`. The first pass to build the string takes O(N) time. The second pass to copy the result back into the array also takes O(N) time. Thus, the total time complexity is O(N).

Space

O(N). The `StringBuilder` can grow up to a size proportional to N. For an input like `['a', 'b', 'c', 'd']`, the compressed string is the same, requiring O(N) extra space. This violates the problem's constraint.

Trade-offs

Pros

Simple to conceptualize and implement.
The logic is very clear and follows the problem description directly.

Cons

Violates the O(1) extra space constraint, making it an invalid solution for this specific problem.
Requires a second pass to copy the data back, which is less efficient than an in-place modification.

The optimal solution uses a two-pointer technique to modify the array in-place, satisfying the constant extra space requirement. We use a read pointer to iterate through the original array and a write pointer to place the compressed characters. Since the compressed version is always shorter or of the same length, the write pointer never surpasses the read pointer, allowing for safe in-place modification.

Algorithm

Initialize writeIndex = 0 and readIndex = 0.
Loop while readIndex is less than the array length.
Inside the loop, identify the current character and count its consecutive occurrences, advancing readIndex past the group.
Write the character to chars[writeIndex] and increment writeIndex.
If the group's count is greater than 1, convert the count to a string.
For each digit in the count string, write it to chars[writeIndex] and increment writeIndex.
After the loop finishes, writeIndex holds the new length of the compressed array. Return writeIndex.

Walkthrough

This algorithm processes the array in a single pass. We maintain two pointers: readIndex and writeIndex. The readIndex scans the array from left to right to identify groups of consecutive characters. The writeIndex points to the next available slot in the chars array where the compressed data should be written. For each group, we first write the character itself. Then, if the group's length is greater than one, we convert the length to its character digits and write them sequentially. The readIndex is advanced to the beginning of the next group, and the process repeats. The final value of writeIndex gives the new length of the array.

1public int compress(char[] chars) {2    int writeIndex = 0;3    int readIndex = 0;4    5    while (readIndex < chars.length) {6        char currentChar = chars[readIndex];7        int count = 0;8        9        // Count consecutive repeating characters10        while (readIndex < chars.length && chars[readIndex] == currentChar) {11            readIndex++;12            count++;13        }14        15        // Write the character16        chars[writeIndex++] = currentChar;17        18        // If count > 1, write the count as characters19        if (count > 1) {20            for (char c : String.valueOf(count).toCharArray()) {21                chars[writeIndex++] = c;22            }23        }24    }25    26    return writeIndex;27}

Complexity

Time

O(N), where N is the length of `chars`. Each character is read exactly once by the `readIndex`, and each character of the output is written exactly once by the `writeIndex`. The overall process is a single pass through the array.

Space

O(1). The algorithm uses a fixed number of variables (`writeIndex`, `readIndex`, `count`, etc.) regardless of the input size. The space used to store the string representation of a count is temporary and bounded by O(log N), which is considered constant for practical purposes and within the problem's constraints.

Trade-offs

Pros

Extremely efficient, with linear time and constant space complexity.
Modifies the array in-place as required by the problem.
It's the optimal solution that meets all constraints.

Cons

The in-place logic with two pointers can be slightly more complex to grasp initially compared to using an auxiliary data structure.

Solutions

Solution

1class Solution {2public3  int compress(char[] chars) {4    int k = 0, n = chars.length;5    for (int i = 0, j = i + 1; i < n;) {6      while (j < n && chars[j] == chars[i]) {7        ++j;8      }9      chars[k++] = chars[i];10      if (j - i > 1) {11        String cnt = String.valueOf(j - i);12        for (char c : cnt.toCharArray()) {13          chars[k++] = c;14        }15      }16      i = j;17    }18    return k;19  }20}

1class Solution {2public:3  int compress(vector<char> &chars) {4    int k = 0, n = chars.size();5    for (int i = 0, j = i + 1; i < n;) {6      while (j < n && chars[j] == chars[i])7        ++j;8      chars[k++] = chars[i];9      if (j - i > 1) {10        for (char c : to_string(j - i)) {11          chars[k++] = c;12        }13      }14      i = j;15    }16    return k;17  }18};

1class Solution:2    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 ''' if a follow up question asking for the compressed result, simply return return chars[:k]; '''

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem