String Compression III

Med

#2810Time: 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: 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.2 companies

Data structures

String

Companies

Qualcomm Affirm

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

1class Solution {2    public String compressedString(String word) {3        StringBuilder comp = new StringBuilder();4        String currentWord = word;5        while (!currentWord.isEmpty()) {6            char c = currentWord.charAt(0);7            int count = 0;8            while (count < currentWord.length() && currentWord.charAt(count) == c) {9                count++;10            }11            12            int chunkSize = Math.min(count, 9);13            comp.append(chunkSize);14            comp.append(c);15            16            currentWord = currentWord.substring(chunkSize);17        }18        return comp.toString();19    }20}

Complexity

Time

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

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.

Trade-offs

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.

An optimal approach is to iterate through the string just once using a pointer. We can use this pointer to keep track of our current position. In each step, we count the number of consecutive identical characters, up to a maximum of 9, forming a chunk. We then append the count and the character to our result and advance the pointer. This avoids expensive string manipulations and multiple passes.

Algorithm

Initialize an empty StringBuilder called comp.
Initialize a pointer i = 0 to traverse the input word.
Loop while i is less than the length of word:
- Store the character at the current position: char c = word.charAt(i).
- Initialize a count = 0 for the current chunk.
- Start a nested while loop that continues as long as i is within bounds, the character at i is c, and count is less than 9.
- Inside the nested loop, increment count and i.
- After the nested loop, append the final count and the character c to comp.
After the main loop finishes, return comp.toString().

Walkthrough

This method processes the string from left to right in a single pass, building the compressed string as it goes. It's efficient because it avoids creating intermediate substrings and re-scanning parts of the string. The core idea is to use a single pointer i that always moves forward, consuming characters as it forms compressed chunks.

1class Solution {2    public String compressedString(String word) {3        StringBuilder comp = new StringBuilder();4        int i = 0;5        int n = word.length();6        while (i < n) {7            char c = word.charAt(i);8            int count = 0;9            // Count consecutive occurrences of character c, up to 910            while (i < n && word.charAt(i) == c && count < 9) {11                count++;12                i++;13            }14            comp.append(count);15            comp.append(c);16        }17        return comp.toString();18    }19}

Complexity

Time

O(N), where N is the length of `word`. The pointer `i` traverses the string from left to right exactly once. Each character is visited a constant number of times, and `StringBuilder.append` operations are amortized O(1).

Space

O(N), where N is the length of the input string. This space is used for the `StringBuilder` to construct the output string. In the worst case (e.g., 'abcde'), the output ('1a1b1c1d1e') can be twice the length of the input.

Trade-offs

Pros

Optimal time complexity of O(N).
Space-efficient as it avoids creating intermediate strings, using a StringBuilder for efficient appends.
Simple and concise implementation through a single pass.

Cons

This approach is optimal for the given constraints, so it has no significant disadvantages.

Solutions

Solution

1class Solution {2public3  String compressedString(String word) {4    StringBuilder ans = new StringBuilder();5    int n = word.length();6    for (int i = 0; i < n;) {7      int j = i + 1;8      while (j < n && word.charAt(j) == word.charAt(i)) {9        ++j;10      }11      int k = j - i;12      while (k > 0) {13        int x = Math.min(9, k);14        ans.append(x).append(word.charAt(i));15        k -= x;16      }17      i = j;18    }19    return ans.toString();20  }21}

1/** * @param {string} word * @return {string} */ var compressedString = function ( word ) { const ans = []; const n = word . length ; for ( let i = 0 ; i < n ; ) { let j = i + 1 ; while ( j < n && word [ j ] === word [ i ]) { ++ j ; } let k = j - i ; while ( k ) { const x = Math . min ( k , 9 ); ans . push ( x + word [ i ]); k -= x ; } i = j ; } return ans . join ( '' ); };

1class Solution {2public:3  string compressedString(string word) {4    string ans;5    int n = word.length();6    for (int i = 0; i < n;) {7      int j = i + 1;8      while (j < n && word[j] == word[i]) {9        ++j;10      }11      int k = j - i;12      while (k > 0) {13        int x = min(9, k);14        ans.push_back('0' + x);15        ans.push_back(word[i]);16        k -= x;17      }18      i = j;19    }20    return ans;21  }22};

1class Solution:2    def compressedString(self, word: str) -> str: g = groupby(word) ans = [] for c, v in g: k = len(list(v)) while k: x = min(9, k) ans . append(str(x) + c) k -= x return "" . join(ans)

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