String Compression III

Medium
1770.

String Compression III

String Compression III is a medium coding problem on strings, asked in Amazon, Google and Microsoft interviews.

Given a string word, compress it with the following procedure. Start with an empty string comp. While word is not empty:

  • remove the longest prefix of word that consists of a single character c repeated at most 9 times;
  • append the length of that prefix (a single digit) followed by c to comp.

Return comp.

Example 1

Input
word = "abcde"
Output
1a1b1c1d1e
Explanation
Every prefix is a single letter.

Example 2

Input
word = "aaaaaaaaaaaaaabb"
Output
9a5a2b
Explanation
Fourteen a's are cut into a block of 9 and a block of 5, then the two b's.

Example 3

Input
word = "z"
Output
1z

Constraints

  • 1 <= word.length <= 2 * 10^5
  • word consists only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word
 * @return {string}
 */
var compressedString = function(word) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

String Compression III — Solution in Python, Java & C++

String Compression III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on strings.

String Compression III is a medium coding problem on strings, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Strings
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a string word, compress it with the following procedure. Start with an empty string comp. While word is not empty:

  • remove the longest prefix of word that consists of a single character c repeated at most 9 times;
  • append the length of that prefix (a single digit) followed by c to comp.

Return comp.

Example 1

Input: word = "abcde"
Output: 1a1b1c1d1e
Explanation: Every prefix is a single letter.

Example 2

Input: word = "aaaaaaaaaaaaaabb"
Output: 9a5a2b
Explanation: Fourteen a's are cut into a block of 9 and a block of 5, then the two b's.

Example 3

Input: word = "z"
Output: 1z

Constraints

  • 1 <= word.length <= 2 * 10^5
  • word consists only of lowercase English letters

Hints for String Compression III

  1. Hint 1

    Walk the string once, measuring the run of equal characters that starts at the current position.

  2. Hint 2

    Cap each run at 9 characters: a longer run is emitted as several blocks.

  3. Hint 3

    Append the count and the character for each block; use a string builder so the output is built in linear time.

How to solve String Compression III

The procedure is a run-length encoding whose counts are capped at a single digit, so a single left-to-right scan that cuts runs at 9 produces the answer.

Approach

  1. Set i = 0.
  2. Advance j from i while j < n, j - i < 9 and word[j] == word[i].
  3. Append the digit j - i and the character word[i]; set i = j and repeat until i == n.

Why it works

At each step the removed prefix is the longest run of one character of length at most 9 — exactly what the loop measures — and the remainder is processed the same way, so the output is the procedure's output.

Complexity

  • Time — O(n)
  • Space — O(n) for the output

Pitfalls

  • A run of 10 or more equal characters must be split: "aaaaaaaaaa" is "9a1a", not "10a".
  • Repeated string concatenation is quadratic in some languages; use a builder.

Reference solution

Python

def compressedString(word: str) -> str:
    parts = []
    n, i = len(word), 0
    while i < n:
        j = i
        while j < n and j - i < 9 and word[j] == word[i]:
            j += 1
        parts.append(str(j - i))
        parts.append(word[i])
        i = j
    return "".join(parts)

Java

public static String compressedString(String word) {
    StringBuilder sb = new StringBuilder();
    int n = word.length(), i = 0;
    while (i < n) {
        int j = i;
        while (j < n && j - i < 9 && word.charAt(j) == word.charAt(i)) j++;
        sb.append(j - i).append(word.charAt(i));
        i = j;
    }
    return sb.toString();
}

C++

string compressedString(string word) {
    string out;
    int n = word.size(), i = 0;
    while (i < n) {
        int j = i;
        while (j < n && j - i < 9 && word[j] == word[i]) j++;
        out += (char) ('0' + (j - i));
        out += word[i];
        i = j;
    }
    return out;
}

JavaScript

var compressedString = function(word) {
    var parts = [], n = word.length, i = 0;
    while (i < n) {
        var j = i;
        while (j < n && j - i < 9 && word[j] === word[i]) j++;
        parts.push(String(j - i), word[i]);
        i = j;
    }
    return parts.join("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings