字符串压缩：解法分析笔记

题目内容：把字符数组按「连续相同字符组」压缩——长度为 1 的组只保留字符，长度大于等于 2 的组写成「字符 + 十进制长度」；结果写回原数组并返回新的有效长度，要求只使用常量额外空间。

题源：LeetCode 443 - 字符串压缩

实现：https://github.com/delight-rs/rust-algorithm/blob/main/src/string/string_compression.rs

一句话概括：用 start 记录当前组的起点、next 扫描组边界、i 记录已经写出的压缩长度；因为「长度为 1 的组不写计数」保证编码后不会变长，写指针始终不越过组起点，可以原地重写。时间 O(n)，额外空间 O(1)。

1. 输入与输出

1.1 输入

1.2 输出

返回压缩后的有效长度（i32），压缩内容写在 chars 的前 返回值 个位置。chars 不会被截断，返回长度之后的内容没有定义，不应读取。

把 chars 划分为极大连续相同字符组 g1, g2, …, gk：
  每组非空；相邻两组的首字符不同

encode(g) = g[0]                    , len(g) = 1
          = g[0] + decimal(len(g))  , len(g) >= 2

输出序列 = encode(g1) + encode(g2) + … + encode(gk)
返回值   = len(输出序列)

这里 decimal(x) 表示 x 的十进制写法，高位在前，例如 12 对应字符 '1'、'2'。

三个容易忽略的点：

• 「极大」意味着分组是唯一的：相邻组不能合并；
• 只有 len(g) >= 2 才写计数，长度为 1 的组永远不写 '1'；
• 返回长度之后的位置仍保留旧字符，但不再属于压缩结果。

1.3 示例

最后一行说明：压缩结果 122 在不知道原始分组的情况下无法唯一解码，这一点在第 5 节会展开。

1.4 边界与约束

• 题面保证：1 <= chars.len() <= 2000；字符范围是字母、数字和符号。压缩后的长度不会超过原长度。
• 代码自己处理：len = 0 时返回 0，len = 1 时返回 1。len = 0 的保护是必要的：如果没有 len <= 1 的提前返回，循环结束后会执行 chars[0] = chars[0]，在空数组上直接 panic。
• 代码隐含假设：chars 是一个合法的 Vec<char>；组长度不超过 usize 范围；返回值用 i32 表示，在 n <= 2000 时不会溢出。
• 关于常量空间：题面要求常量额外空间。当前实现用 count.to_string() 生成计数字符串，每个完整组会申请一次很小的堆内存（n <= 2000 时最多 4 字节），从严格意义上说是 O(log n) 而不是零分配；对本题数据规模没有实际影响，去掉分配的方法见 3.4。

2. 文件中的实现

文件里只有一个实现：Solution::compress，配合私有的辅助函数 Solution::modify。整体是「顺序扫描组边界 + 原地写出编码结果」的行程编码（run-length encoding）。

2.1 三个下标的分工

i 和 start 的关系是算法能原地工作的核心：始终有 i <= start，写指针不会越过当前组的起点。证明见 2.4。

2.2 主循环

let mut i = 0;
let mut start = 0;
let mut next = 1;

while next < len {
   
    if chars[start] != chars[next] {
   
        Self::modify(chars, &mut i, start, next);
        start = next;
    }
    next += 1;
}

Self::modify(chars, &mut i, start, next);
i as i32

执行过程：

1. next 从 1 开始向右扫描；只要 chars[next] 和当前组的首字符 chars[start] 相同，当前组就还没结束，next 继续右移。
2. 遇到不同字符时，区间 [start, next) 就是一个完整的组，调用 modify 把它写到写指针 i 处。
3. start 移动到 next，开始处理下一组。
4. 循环结束时 next == len，最后一个组 [start, len) 还没有写出，需要在循环外补一次 modify。
5. 返回 i，它等于写出的字符总数。

辅助函数 modify 负责写出一个组：

fn modify(chars: &mut Vec<char>, i: &mut usize, start: usize, next: usize) {
   
    chars[*i] = chars[start];
    *i += 1;

    let count = next - start;
    if count >= 2 {
   
        for c in count.to_string().chars() {
   
            chars[*i] = c;
            *i += 1;
        }
    }
}

• 先写组代表字符 chars[start]；
• 组长度 count = next - start 至少为 1；
• 只有 count >= 2 才写十进制计数，to_string() 天然按高位到低位产出字符；
• i 用 &mut usize 传入，是因为辅助函数需要把写指针的推进结果带回主循环。

2.3 状态追踪

以官方示例 ['a','a','b','b','c','c','c'] 为例，len = 7：

最后一行下标 6 的 'c' 是原数组的残留字符，返回值 6 表示它不属于压缩结果。

再看多位数计数：['a'] 后接 12 个 'b'，len = 13：

2.4 正确性说明

循环不变量（每次判断 while next < len 之前成立）：

1. 0 <= i <= start < next <= len；
2. chars[0..start] 中的所有完整组都已编码，并且编码结果恰好是 chars[0..i]；
3. chars[start..next] 内的字符全部等于 chars[start]，即 [start, next) 是当前组已经扫描到的部分。

初始时 i = start = 0、next = 1，第 2 条对空区间成立，第 3 条对单个字符成立。每轮如果字符相同，只把 next 加 1，第 3 条保持；如果字符不同，modify 写出 [start, next) 这一组，随后 start 更新为 next、i 增加该组的编码长度，第 2 条保持，第 3 条在新组的一个字符上重新成立。

写指针为什么安全：设一个组长度为 L，编码长度为

enc(L) = 1                    , L = 1
       = 1 + digits(L)        , L >= 2

其中 digits(L) 是 L 的十进制位数。对 L = 1，enc(1) = 1 = L；对 L >= 2，digits(L) <= L - 1，所以 enc(L) = 1 + digits(L) <= L。因此在写一个组之前，如果 i <= start，写完之后

i_new = i + enc(L) <= start + L = next = start_new

新组起点更新为 next，i <= start 继续成立。并且所有写入位置都在 [i, i_new) 内，最大下标 i_new - 1 <= next - 1 < next，不会覆盖 [next, len) 中尚未扫描的字符。

另外，modify 在写任何字符之前先读取 chars[start]，所以即使 i == start（例如每个组长度都是 2 时会出现），先读后写也不会丢失当前组的首字符。组长度只由下标 next - start 计算，不依赖组内字符，因此写出计数时覆盖当前组自己的字符也没有影响。

终止时：next 每轮加 1，最终等于 len；循环外的 modify 写出最后一个组。此时 i 等于所有组编码长度之和，正好是输出序列的长度，返回 i 满足定义。

易错点：

1. 不能给长度为 1 的组写 '1'。 这会让编码长度从 1 变成 2，写指针可能越过未读数据。以 ['a','b'] 为例，如果给第一个组写 '1'，i 会变成 2，处理第二个组时执行 chars[2] = 'b'，直接数组越界 panic。count >= 2 不是可选的优化，而是原地算法的前提。
2. 循环结束后必须补写最后一个组。 组的结束是靠「遇到不同字符」触发的，最后一组后面没有不同字符，只能在循环外处理。
3. 计数必须是高位在前。 count.to_string() 的顺序正确；如果改成用 count % 10 逐位写，会得到倒序的计数，需要先算位数再从右往左填。
4. 返回值是 usize 到 i32 的转换。 本题 n <= 2000，转换安全；如果推广到任意长度，需要处理超出 i32 的情况。

3. 为什么能想到这个方案

3.1 最直白的解法

按定义扫描分组，把编码结果写到一个新的 Vec<char> 或 String，最后拷回 chars：

out = []
扫描 chars，得到每个组 (c, L)
out.extend(encode(c, L))
chars[..out.len()].copy_from_slice(&out)
return out.len()

• 时间 O(n)，空间 O(n)；
• 逻辑直接，适合作为对拍基准；
• 不满足题目的常量额外空间要求；在固定大小的缓冲区或嵌入式场景里也没有条件分配这么大的临时数组。

另一种看起来「原地」的写法是用 Vec::insert 在数组中插入计数位、用 drain 删除多余的旧字符。每次插入或删除都需要移动 O(n) 个元素，最坏 O(n²)；而且 insert 可能触发 Vec 扩容，底层缓冲区会被重新分配，同样不满足常量空间。

3.2 优化尝试及失败原因

一个自然的想法是：既然要原地压缩，那就每个组都写「字符 + 计数」。它的失败原因是编码规则本身可能膨胀：

"abc" 按「总是写计数」编码 → "a1b1c1" ，长度 6 > 3

一旦输出长度可能超过输入长度，原地写就必然覆盖尚未读取的字符；要避免覆盖，只能扩大数组或换到新缓冲区，常量空间的要求随之失效。

关键转折是修改编码规则：只有组长度大于等于 2 时才写计数。这样每个组的编码长度都不超过组长度：

输出不膨胀，写指针就永远不会越过读指针，压缩结果可以直接写回输入数组。这个规则既符合题目要求，也是原地算法的前提，而不只是为了少写一个字符。

3.3 换视角拆解

把数组看成四个区域，三个指针把它们分开：

下标:  0                i          start          next              len
       | 已写出的压缩结果 | 可覆盖的旧字符 | 当前字符组 | 尚未扫描的字符 |

当当前组结束时，它的编码从 i 开始写出。由于 enc(L) <= L，写完的位置不会到达 next，因此尚未扫描的区域保持完整。这也是为什么不需要额外的缓冲区：压缩结果只是把「已经读过的部分」重新排列，占用空间不超过原来读过的内容。

另一种可行写法是从数组后往前填：先统计压缩后的总长度 total，再从后往前找出每个组并写出。因为 total <= n，同样不会覆盖未处理的数据。但反向扫描要先定位组的起点和终点，计数也要按正确顺序写，代码比正向写法复杂；当前实现利用「不膨胀」直接正向覆盖，更容易理解。

3.4 空间优化

当前实现的固定状态只有 i、start、next、len 等几个整数，额外空间是 O(1)。唯一的动态分配来自 count.to_string()：每组申请一个很小的 String，长度至多 digits(n)，本题最多 4 字节。

如果要求严格零分配，可以先算出 count 的位数，再从右往左把数字填进 chars：

let mut digits = 1;
let mut t = count;
while t >= 10 {
   
    t /= 10;
    digits += 1;
}

let mut pos = *i + digits;
let mut t = count;
while pos > *i {
   
    pos -= 1;
    chars[pos] = char::from(b'0' + (t % 10) as u8);
    t /= 10;
}
*i += digits;

这段代码只使用几个整数变量，仍然是 O(1) 额外空间；先算位数是为了知道写入区间的右端，再从右往左逐位填写，得到高位在前的计数。

3.5 可迁移的模板

当「逐组重写」的输出块长度不超过输入块长度，并且组边界可以用一次顺序扫描确定时，可以用「组起点 + 扫描指针 + 写指针」在 O(n) 时间、O(1) 额外空间完成原地改写。

这一类问题的共同点是写指针永远不会追上读指针：

反过来，只要输出块可能比输入块长，就不能直接套用这个模板，必须先扩容、换缓冲区，或者改用「从后往前写」并确认总长度不超过原数组。

4. 复杂度对比

补充说明：

• 扫描阶段比较 n - 1 次；写出阶段的总字符数为 sum(enc(Lj)) <= n；两组操作都是线性，总时间 O(n)。
• 额外空间不包含输出，因为输出直接写在输入数组内；chars 的容量和长度都没有变化，代码只对已有下标赋值。
• 最坏情况：全部字符相同 → 只有一组，写出 1 + digits(n) 个字符；全部字符不同 → n 个长度为 1 的组，每个组写 1 个字符。两种情况都是 O(n)。
• 可并行化程度有限：相邻字符比较、每组长度和写出偏移可以用前缀和预计算，但原地写回存在重叠，通常需要分块处理后再并行。

5. 实际应用场景

行程编码（RLE）是最简单的无损压缩之一，核心就是「把连续重复的值替换成值和次数」。本题的原地版本适合内存受限、只需要压缩不需要随机访问的场景。

工程注意：

• 编码规则必须保证不膨胀。 如果格式要求每个组都写计数，长度为 1 的组会从 1 个字符变成 2 个字符，必须预留额外空间或动态扩容；本题通过「长度 1 不写计数」避免了这个问题。
• 解码可能不唯一。 当输入字符本身包含数字时，压缩结果会出现歧义。例如 ['1','1','2'] 压缩为 122，无法仅凭结果判断它是「'1' 重复 22 次」「'1' 重复 2 次后跟 '2'」，还是「'1' 后跟 '2' 重复 2 次」。实际格式通常把「值流」和「计数流」分开存储，或者使用转义、固定宽度计数来消除歧义。本题只要求压缩，不要求解码，所以不受影响。
• 计数宽度要明确。 组长度可能很大，固定十进制位数便于随机访问但浪费空间，变长整数（varint）更省空间但解码需要逐字节判断；本题 n <= 2000，最多 4 位。
• 适合流式处理。 逐组处理，组结束即可输出，内存中只需要保存当前字符和计数。
• 可结合 SIMD/并行。 先并行判断每个位置是否与前一位置相同，再用前缀和得到组边界和每组的写出偏移；不过原地写回需要额外的分块策略。

6. 延伸与变体

7. 实现

// CN: https://leetcode.cn/problems/string-compression/description/
// EN: https://leetcode.com/problems/string-compression/?envType=study-plan-v2&envId=leetcode-75

struct Solution {
   }

impl Solution {
   
    pub fn compress(chars: &mut Vec<char>) -> i32 {
   
        let len = chars.len();

        if len <= 1 {
   
            return len as i32;
        }

        let mut i = 0;
        let mut start = 0;
        let mut next = 1;

        while next < len {
   
            if chars[start] != chars[next] {
   
                Self::modify(chars, &mut i, start, next);
                start = next;
            }

            next += 1;
        }

        Self::modify(chars, &mut i, start, next);

        i as i32
    }

    fn modify(chars: &mut Vec<char>, i: &mut usize, start: usize, next: usize) {
   
        chars[*i] = chars[start];
        *i += 1;

        let count = next - start;
        if count >= 2 {
   
            for c in count.to_string().chars() {
   
                chars[*i] = c;
                *i += 1;
            }
        }
    }
}

8. 现有测试覆盖评价

已覆盖：

• 官方示例 1、2、3；
• 全部字符不同、只有单字符、大小写混合、输入字符本身是数字；
• 组长度 10 和 11，覆盖「一位数计数」到「两位数计数」的边界；
• 两个多位数计数组合（a12b10）；
• 最大长度 2000 个相同字符，覆盖四位数计数 x2000。

可补强：

• 空数组：Solution::compress(&mut vec![]) 应返回 0。代码有 len <= 1 保护，但没有测试覆盖这个分支。
• i 与 start 相等的场景：['a','a','b','b'] 应返回 4，结果为 a2b2。第一组写完后 i == start == 2，可以验证「先读后写」和写指针到达组起点的等号情况。
• 三位数计数边界：100 个相同字符应压缩为 a100，返回 4。当前测试从 11 直接跳到 2000，没有覆盖 99 到 100 的位数变化。
• 位于开头或结尾的单字符组：例如 ['a','b','b'] → ab2、['a','a','b'] → a2b，用于确认单字符组不写计数且后续组仍然正确。
• 随机对拍：用「新建缓冲区」的朴素实现作为基准，随机生成包含字母、数字、符号的字符数组，比较返回长度和前缀内容。
• 不变量检查：可以在测试中断言返回值不大于输入长度；当前测试只比较 chars[..len]，没有读取残留区域，这一点是正确的。

9. 小结