String Compression III

MEDIUM

Description

Given a string word, compress it using the following algorithm:

Begin with an empty string comp. While word is not empty, use the following operation:
- Remove a maximum length prefix of word made of a single character c repeating at most 9 times.
- Append the length of the prefix followed by c to comp.

Return the string comp.

Example 1:

Input: word = "abcde"

Output: "1a1b1c1d1e"

Explanation:

Initially, comp = "". Apply the operation 5 times, choosing "a", "b", "c", "d", and "e" as the prefix in each operation.

For each prefix, append "1" followed by the character to comp.

Example 2:

Input: word = "aaaaaaaaaaaaaabb"

Output: "9a5a2b"

Explanation:

Initially, comp = "". Apply the operation 3 times, choosing "aaaaaaaaa", "aaaaa", and "bb" as the prefix in each operation.

For prefix "aaaaaaaaa", append "9" followed by "a" to comp.
For prefix "aaaaa", append "5" followed by "a" to comp.
For prefix "bb", append "2" followed by "b" to comp.

Constraints:

1 <= word.length <= 2 * 10⁵
word consists only of lowercase English letters.

Approaches

Checkout 2 different approaches to solve String Compression III. Click on different approaches to view the approach and algorithm in detail.

Naive Simulation with Substrings

This approach directly implements the logic described in the problem statement. It works by repeatedly identifying the next chunk to compress, appending its compressed form to the result, and then creating a new, shorter string for the remaining part of the word. This process is repeated until the entire string is consumed.

Algorithm

Initialize comp as an empty StringBuilder.
Let currentWord be a copy of the input word.
Loop while currentWord is not empty:
- Get the first character c = currentWord.charAt(0).
- Find count, the length of the prefix of currentWord consisting only of character c.
- Determine the size of the chunk to process: chunkSize = min(count, 9).
- Append chunkSize and c to comp.
- Update currentWord by creating a new substring that excludes the processed chunk: currentWord = currentWord.substring(chunkSize).
Return the string representation of comp.

This method simulates the compression process step-by-step as described. While conceptually simple because it's a literal translation of the problem, it suffers from significant performance issues due to the way strings are handled in many programming languages like Java, where they are immutable. The repeated creation of new substrings is a costly operation.

class Solution {
    public String compressedString(String word) {
        StringBuilder comp = new StringBuilder();
        String currentWord = word;
        while (!currentWord.isEmpty()) {
            char c = currentWord.charAt(0);
            int count = 0;
            while (count < currentWord.length() && currentWord.charAt(count) == c) {
                count++;
            }
            
            int chunkSize = Math.min(count, 9);
            comp.append(chunkSize);
            comp.append(c);
            
            currentWord = currentWord.substring(chunkSize);
        }
        return comp.toString();
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the length of `word`. The `substring` operation is the bottleneck. In each iteration of the `while` loop, creating a substring takes time proportional to the length of the new string. In the worst-case scenario (e.g., a string with no repeating characters like 'abcde'), the loop runs N times, and the substring operations result in a quadratic time complexity.Space Complexity: O(N^2) in the worst case. Although the final output string is O(N), the cumulative space for all intermediate substrings created during the loop can be quadratic. For an input of length N, strings of length approximately N-1, N-2, ..., 1 are created.

Pros and Cons

Pros:

Very straightforward to implement as it's a direct translation of the problem description.

Cons:

Highly inefficient with a time complexity of O(N^2) in the worst case.
Creates many temporary string objects, leading to high memory usage and garbage collector overhead.
Likely to fail on large inputs with a 'Time Limit Exceeded' (TLE) error.

Code Solutions

Checking out 4 solutions in different languages for String Compression III. Click on different languages to view the code.

class Solution {
public
  String compressedString(String word) {
    StringBuilder ans = new StringBuilder();
    int n = word.length();
    for (int i = 0; i < n;) {
      int j = i + 1;
      while (j < n && word.charAt(j) == word.charAt(i)) {
        ++j;
      }
      int k = j - i;
      while (k > 0) {
        int x = Math.min(9, k);
        ans.append(x).append(word.charAt(i));
        k -= x;
      }
      i = j;
    }
    return ans.toString();
  }
}

Video Solution

Watch the video walkthrough for String Compression III

Data Structures:

String

Companies:

Qualcomm |Affirm |