Scale Engineer

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 SystemsExpediaGoldman SachsIBM

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.

public int compress(char[] chars) {    if (chars == null || chars.length == 0) {        return 0;    }    StringBuilder sb = new StringBuilder();    int i = 0;    while (i < chars.length) {        char currentChar = chars[i];        int count = 0;        int j = i;        while (j < chars.length && chars[j] == currentChar) {            j++;            count++;        }        sb.append(currentChar);        if (count > 1) {            sb.append(count);        }        i = j;    }        char[] compressedChars = sb.toString().toCharArray();    for (int k = 0; k < compressedChars.length; k++) {        chars[k] = compressedChars[k];    }        return sb.length();}

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.

Solutions

class Solution {public  int compress(char[] chars) {    int k = 0, n = chars.length;    for (int i = 0, j = i + 1; i < n;) {      while (j < n && chars[j] == chars[i]) {        ++j;      }      chars[k++] = chars[i];      if (j - i > 1) {        String cnt = String.valueOf(j - i);        for (char c : cnt.toCharArray()) {          chars[k++] = c;        }      }      i = j;    }    return 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 →

Next problem