String Compression III
Problem
Compress word into a string comp. While word is not empty, remove a maximum-length prefix made of a single character c repeating at most 9 times, then append the length of that prefix followed by c to comp. Return comp.
word = "aaaaaaaaaaaaaabb""9a5a2b"def compressedString(word):
comp = []
i, n = 0, len(word)
while i < n:
c = word[i] # character of this run
cnt = 0
# extend while same char, capped at 9
while i < n and word[i] == c and cnt < 9:
cnt += 1
i += 1
comp.append(str(cnt)) # length of the prefix
comp.append(c) # the character
return "".join(comp)function compressedString(word) {
let comp = "";
let i = 0, n = word.length;
while (i < n) {
const c = word[i]; // character of this run
let cnt = 0;
// extend while same char, capped at 9
while (i < n && word[i] === c && cnt < 9) {
cnt++;
i++;
}
comp += String(cnt) + c; // count then character
}
return comp;
}String compressedString(String word) {
StringBuilder comp = new StringBuilder();
int i = 0, n = word.length();
while (i < n) {
char c = word.charAt(i); // character of this run
int cnt = 0;
// extend while same char, capped at 9
while (i < n && word.charAt(i) == c && cnt < 9) {
cnt++;
i++;
}
comp.append(cnt).append(c);
}
return comp.toString();
}string compressedString(string word) {
string comp;
int i = 0, n = word.size();
while (i < n) {
char c = word[i]; // character of this run
int cnt = 0;
// extend while same char, capped at 9
while (i < n && word[i] == c && cnt < 9) {
cnt++;
i++;
}
comp += to_string(cnt) + c;
}
return comp;
}Explanation
This is run-length encoding with one twist: each run we emit is capped at length 9, because the count must be a single digit.
We scan the string left to right with a pointer i. Each outer loop starts a new run: we record the current character c = word[i] and a counter cnt = 0.
The inner loop advances i while three things hold: we are still inside the string, the character still equals c, and we have not yet counted 9 of them. The cap cnt < 9 is what makes a long run split into chunks — 14 identical characters become a 9-chunk and then a 5-chunk.
When the inner loop stops, we append the digit cnt followed by the character c to the output, then the outer loop begins the next run wherever i now points.
Greedy works here because taking the longest legal prefix every time is always optimal: a single count + character pair is the cheapest possible encoding of up to 9 identical characters, so there is never a reason to take fewer.
Example: "aaaaaaaaaaaaaabb". The first run of a’s hits the cap at 9 → "9a". The next run takes the remaining 5 a’s → "5a". Finally 2 b’s → "2b". Result: "9a5a2b".