Scale Engineer

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
QualcommAffirm

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 * 105
  • 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.

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

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.

Solutions

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