LeetCode 3163: String Compression III (Run-Length Chunks Capped at 9)
LeetCode 3163StringRun-Length EncodingGreedyToday we solve LeetCode 3163 - String Compression III.
Source: https://leetcode.com/problems/string-compression-iii/
English
Problem Summary
Given a lowercase string word, build its compressed form by repeatedly taking a maximal run of identical letters from left to right, but each emitted block can encode at most 9 characters. For each block, append count + character.
Key Insight
This is run-length encoding with a hard cap of 9 per block. So each run of length k becomes k // 9 full blocks plus one remainder block if needed.
Brute Force and Limitations
Manually slicing and rebuilding substrings for every character transition works, but unnecessary substring operations can make code noisy and less efficient.
Optimal Algorithm Steps
1) Scan with index i.
2) Find the run end j where characters stop matching.
3) Let run length be len = j - i.
4) While len > 9, emit 9 + char and subtract 9.
5) Emit final len + char.
6) Move i = j and continue.
Complexity Analysis
Time: O(n).
Space: O(n) for output.
Common Pitfalls
- Forgetting the cap: emitting 12a is invalid; must be 9a3a.
- Miscounting when a long run spans multiple capped blocks.
- Using the wrong output order (must be digit first, then character).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String compressedString(String word) {
StringBuilder ans = new StringBuilder();
int n = word.length();
int i = 0;
while (i < n) {
char c = word.charAt(i);
int j = i;
while (j < n && word.charAt(j) == c) {
j++;
}
int len = j - i;
while (len > 9) {
ans.append('9').append(c);
len -= 9;
}
ans.append((char)('0' + len)).append(c);
i = j;
}
return ans.toString();
}
}func compressedString(word string) string {
n := len(word)
out := make([]byte, 0, n)
for i := 0; i < n; {
c := word[i]
j := i
for j < n && word[j] == c {
j++
}
length := j - i
for length > 9 {
out = append(out, '9', c)
length -= 9
}
out = append(out, byte('0'+length), c)
i = j
}
return string(out)
}class Solution {
public:
string compressedString(string word) {
string ans;
ans.reserve(word.size() * 2);
for (int i = 0; i < (int)word.size();) {
char c = word[i];
int j = i;
while (j < (int)word.size() && word[j] == c) {
++j;
}
int len = j - i;
while (len > 9) {
ans.push_back('9');
ans.push_back(c);
len -= 9;
}
ans.push_back(char('0' + len));
ans.push_back(c);
i = j;
}
return ans;
}
};class Solution:
def compressedString(self, word: str) -> str:
n = len(word)
out = []
i = 0
while i < n:
c = word[i]
j = i
while j < n and word[j] == c:
j += 1
length = j - i
while length > 9:
out.append('9')
out.append(c)
length -= 9
out.append(str(length))
out.append(c)
i = j
return ''.join(out)var compressedString = function(word) {
const out = [];
for (let i = 0; i < word.length;) {
const c = word[i];
let j = i;
while (j < word.length && word[j] === c) {
j++;
}
let len = j - i;
while (len > 9) {
out.push('9', c);
len -= 9;
}
out.push(String(len), c);
i = j;
}
return out.join('');
};中文
题目概述
给定一个仅含小写字母的字符串 word，从左到右按连续相同字符分组压缩。但每个压缩块的计数最多只能是 9。每个压缩块格式为 数量 + 字符。
核心思路
本质是“带 9 上限”的游程编码。对于长度为 k 的连续段，要拆成若干个长度 9 的块，再加一个不足 9 的尾块。
暴力解法与不足
如果每次都切片子串再拼接，逻辑上可行，但会引入不必要的字符串复制，代码可读性也较差。
最优算法步骤
1）用指针 i 扫描字符串。
2）找到当前连续段终点 j。
3）长度 len = j - i。
4）当 len > 9 时，输出 9 + 字符 并减 9。
5）输出最后一个 len + 字符。
6）令 i = j 继续下一段。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)（输出缓冲）。
常见陷阱
- 忘记 9 的上限，错误输出 12a，正确应为 9a3a。
- 长连续段拆分时计数更新写错。
- 输出顺序写反，必须是“数字在前，字符在后”。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String compressedString(String word) {
StringBuilder ans = new StringBuilder();
int n = word.length();
int i = 0;
while (i < n) {
char c = word.charAt(i);
int j = i;
while (j < n && word.charAt(j) == c) {
j++;
}
int len = j - i;
while (len > 9) {
ans.append('9').append(c);
len -= 9;
}
ans.append((char)('0' + len)).append(c);
i = j;
}
return ans.toString();
}
}func compressedString(word string) string {
n := len(word)
out := make([]byte, 0, n)
for i := 0; i < n; {
c := word[i]
j := i
for j < n && word[j] == c {
j++
}
length := j - i
for length > 9 {
out = append(out, '9', c)
length -= 9
}
out = append(out, byte('0'+length), c)
i = j
}
return string(out)
}class Solution {
public:
string compressedString(string word) {
string ans;
ans.reserve(word.size() * 2);
for (int i = 0; i < (int)word.size();) {
char c = word[i];
int j = i;
while (j < (int)word.size() && word[j] == c) {
++j;
}
int len = j - i;
while (len > 9) {
ans.push_back('9');
ans.push_back(c);
len -= 9;
}
ans.push_back(char('0' + len));
ans.push_back(c);
i = j;
}
return ans;
}
};class Solution:
def compressedString(self, word: str) -> str:
n = len(word)
out = []
i = 0
while i < n:
c = word[i]
j = i
while j < n and word[j] == c:
j += 1
length = j - i
while length > 9:
out.append('9')
out.append(c)
length -= 9
out.append(str(length))
out.append(c)
i = j
return ''.join(out)var compressedString = function(word) {
const out = [];
for (let i = 0; i < word.length;) {
const c = word[i];
let j = i;
while (j < word.length && word[j] === c) {
j++;
}
let len = j - i;
while (len > 9) {
out.push('9', c);
len -= 9;
}
out.push(String(len), c);
i = j;
}
return out.join('');
};
Comments