LeetCode 443: String Compression (Two Pointers In-Place Write)
LeetCode 443StringTwo PointersToday we solve LeetCode 443 - String Compression.
Source: https://leetcode.com/problems/string-compression/
English
Problem Summary
Given a character array chars, compress consecutive equal characters in place. For each group, write the character once, and if count > 1, write decimal digits of the count. Return the new length after compression.
Key Insight
Use two pointers: read scans groups, write writes compressed output back into the same array. The prefix chars[0..write-1] is always valid compressed data for already-processed groups.
Algorithm
- Set write = 0, read = 0.
- While read < n, find the maximal group [read, j) where all chars are equal.
- Write group character to chars[write], then write++.
- If group size cnt = j - read is greater than 1, convert cnt to string and write each digit.
- Move read = j and continue.
- Return write.
Complexity Analysis
Let n be the array length.
Time: O(n).
Space: O(1) extra (ignoring temporary count-string digits).
Common Pitfalls
- Forgetting that count 1 should not append digit 1.
- Writing count as one char instead of multiple digits (e.g. 12 must write '1','2').
- Using extra output array and violating in-place constraint.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int compress(char[] chars) {
int n = chars.length;
int write = 0;
int read = 0;
while (read < n) {
char ch = chars[read];
int j = read;
while (j < n && chars[j] == ch) j++;
chars[write++] = ch;
int cnt = j - read;
if (cnt > 1) {
for (char d : String.valueOf(cnt).toCharArray()) {
chars[write++] = d;
}
}
read = j;
}
return write;
}
}func compress(chars []byte) int {
n := len(chars)
write, read := 0, 0
for read < n {
ch := chars[read]
j := read
for j < n && chars[j] == ch {
j++
}
chars[write] = ch
write++
cnt := j - read
if cnt > 1 {
for _, d := range strconv.Itoa(cnt) {
chars[write] = byte(d)
write++
}
}
read = j
}
return write
}class Solution {
public:
int compress(vector<char>& chars) {
int n = (int)chars.size();
int write = 0, read = 0;
while (read < n) {
char ch = chars[read];
int j = read;
while (j < n && chars[j] == ch) ++j;
chars[write++] = ch;
int cnt = j - read;
if (cnt > 1) {
string s = to_string(cnt);
for (char d : s) chars[write++] = d;
}
read = j;
}
return write;
}
};class Solution:
def compress(self, chars: List[str]) -> int:
n = len(chars)
write = 0
read = 0
while read < n:
ch = chars[read]
j = read
while j < n and chars[j] == ch:
j += 1
chars[write] = ch
write += 1
cnt = j - read
if cnt > 1:
for d in str(cnt):
chars[write] = d
write += 1
read = j
return writevar compress = function(chars) {
const n = chars.length;
let write = 0;
let read = 0;
while (read < n) {
const ch = chars[read];
let j = read;
while (j < n && chars[j] === ch) j++;
chars[write++] = ch;
const cnt = j - read;
if (cnt > 1) {
for (const d of String(cnt)) {
chars[write++] = d;
}
}
read = j;
}
return write;
};中文
题目概述
给定字符数组 chars，要求你进行原地压缩：同一字符连续出现时只写一个字符；若出现次数大于 1，再把次数按十进制逐位写入数组。返回压缩后长度。
核心思路
使用双指针：read 负责扫描分组，write 负责把压缩结果写回原数组。始终保证 chars[0..write-1] 是已处理前缀的正确压缩结果。
算法步骤
- 初始化 write = 0、read = 0。
- 以 read 为起点找到连续相同字符区间 [read, j)。
- 先写入该字符本身。
- 若计数 cnt = j-read > 1，将 cnt 转成字符串并逐位写入。
- 更新 read = j 继续下一组。
- 扫描结束返回 write。
复杂度分析
设数组长度为 n。
时间复杂度：O(n)。
空间复杂度：O(1) 额外空间（不计计数字符串临时位数）。
常见陷阱
- 次数为 1 时错误写入字符 '1'。
- 多位数字计数处理错误（如 12 应写成 '1','2'）。
- 使用额外数组输出，违反题目原地要求。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int compress(char[] chars) {
int n = chars.length;
int write = 0;
int read = 0;
while (read < n) {
char ch = chars[read];
int j = read;
while (j < n && chars[j] == ch) j++;
chars[write++] = ch;
int cnt = j - read;
if (cnt > 1) {
for (char d : String.valueOf(cnt).toCharArray()) {
chars[write++] = d;
}
}
read = j;
}
return write;
}
}func compress(chars []byte) int {
n := len(chars)
write, read := 0, 0
for read < n {
ch := chars[read]
j := read
for j < n && chars[j] == ch {
j++
}
chars[write] = ch
write++
cnt := j - read
if cnt > 1 {
for _, d := range strconv.Itoa(cnt) {
chars[write] = byte(d)
write++
}
}
read = j
}
return write
}class Solution {
public:
int compress(vector<char>& chars) {
int n = (int)chars.size();
int write = 0, read = 0;
while (read < n) {
char ch = chars[read];
int j = read;
while (j < n && chars[j] == ch) ++j;
chars[write++] = ch;
int cnt = j - read;
if (cnt > 1) {
string s = to_string(cnt);
for (char d : s) chars[write++] = d;
}
read = j;
}
return write;
}
};class Solution:
def compress(self, chars: List[str]) -> int:
n = len(chars)
write = 0
read = 0
while read < n:
ch = chars[read]
j = read
while j < n and chars[j] == ch:
j += 1
chars[write] = ch
write += 1
cnt = j - read
if cnt > 1:
for d in str(cnt):
chars[write] = d
write += 1
read = j
return writevar compress = function(chars) {
const n = chars.length;
let write = 0;
let read = 0;
while (read < n) {
const ch = chars[read];
let j = read;
while (j < n && chars[j] === ch) j++;
chars[write++] = ch;
const cnt = j - read;
if (cnt > 1) {
for (const d of String(cnt)) {
chars[write++] = d;
}
}
read = j;
}
return write;
};
Comments