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
wordthat consists of a single charactercrepeated at most 9 times; - append the length of that prefix (a single digit) followed by
ctocomp.
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^5word consists only of lowercase English letters
Hints for String Compression III
Hint 1
Walk the string once, measuring the run of equal characters that starts at the current position.
Hint 2
Cap each run at 9 characters: a longer run is emitted as several blocks.
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
- Set
i = 0. - Advance
jfromiwhilej < n,j - i < 9andword[j] == word[i]. - Append the digit
j - iand the characterword[i]; seti = jand repeat untili == 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