String Compression
你会得到一个由英文字母组成的字符串 s。对它进行压缩：将每段连续出现两次或更多次的相同字母替换为该字母后接这段重复的长度，并保留单独出现的字母不变。例如，aabccc 会变成 a2bc3。返回压缩后的字符串。
大写和小写字母是不同的字母：aA 是两段长度为 1 的连续字母。
函数
- sstring
- 要压缩的字符串，只包含英文字母
- 返回值string
- 压缩后的字符串，当长度大于 1 时，将每段连续字符写成该字符加上其长度
约束条件
1 ≤ s.length ≤ 2 × 104s只包含英文字母，即a到z和A到Z。- 游程长度以十进制表示，可以有多位数字。
示例
- 输入
- s = "aabccc"
- 输出
- "a2bc3"
- 解释
- 连续相同字符分别是
aa、b和ccc。它们会变成a2、b（单个字母不加计数）和c3。
- 输入
- s = "abbbbbbbbbbbb"
- 输出
- "ab12"
- 解释
- 一个
a，然后是十二个b。长度 12 写成字符1和2，所以结果是ab12。
- 输入
- s = "zzZZZ"
- 输出
- "z2Z3"
- 解释
- 小写字母
z和大写字母Z是不同的字母，所以这里是两个连续的z，后面跟着三个连续的Z：z2Z3。
进阶
反过来写：给定一个压缩字符串，例如 ab12，还原原始字符串。如何读取由多位数字组成的计数？
提示
逐个打开提示，每个都会多透露一点。
把
s看作一排方块，每个方块由重复的同一个字母组成。要写出一个方块，你需要知道它的哪两个信息？每个区块都需要记录它的字母和长度。用一个索引记录区块的起始位置，再向前移动第二个索引，只要它看到的还是同一个字母就继续移动；两个索引之间的距离就是区块的长度。
在一段连续字符的开头保留
i，移动j，直到s[j]不同或字符串结束。写出s[i]，然后在j-i大于 1 时将其写成十进制文本，再将i跳到j。像 12 这样的长度是两个字符。
题解
找出每段相同字母的起始位置和结束位置，然后将它的长度写成文本。只有一个字母的一段不写计数，计数可以有多位数字。用两个索引，一个指向每段的起始位置，另一个扫描到该段的末尾，只需遍历一遍即可完成。
收集这些运行记录，然后写下来
思路
先把每段连续字符记录为字母和长度组成的对：对于 aabccc，记录为 (a, 2)、(b, 1)、(c, 3)。每个字母要么延长最后一段，要么开启新的一段。然后写出每段的字母，长度大于 1 时再写出长度。
两次遍历的时间复杂度都是 O(n)。如果相邻字符都不相同，列表最多会有 n 段，因此需要 O(n) 的额外空间。
算法
- 创建一个空的连续段列表。
- 遍历
s中的每个字母：如果最后一个连续段的字母相同，就将它的长度加 1；否则追加一个长度为 1 的新连续段。 - 对于每个连续段，先写出它的字母；如果长度大于 1，再将长度写成十进制文本。
def compress(s):
# First pass: collect the runs as [letter, length] pairs
runs = []
for ch in s:
if runs and runs[-1][0] == ch:
runs[-1][1] += 1
else:
runs.append([ch, 1])
# Second pass: write each run, with its length when it is more than 1
parts = []
for letter, length in runs:
parts.append(letter)
if length > 1:
parts.append(str(length))
return "".join(parts)双指针遍历每个连续段
思路
让 i 指向当前连续段的第一个字母，并在 s[j] 等于 s[i] 时不断向前移动 j。当 j 停下时，它要么遇到了不同的字母，要么到达了末尾，此时连续段的长度是 j-i。写出结果，并设置 i = j。对于 abbbbbbbbbbbb，j 先在 1 处停下，得到 a，然后在 13 处停下，得到 b12。
最后一个连续段不需要特殊处理，因为内层循环会在字符串末尾停下。j 只会向前移动，因此时间复杂度是 O(n)。除了结果之外，你只需保留两个索引。R 和 Swift 版本会先把 s 拆分成字符数组，因此会使用 O(n) 的额外空间。
算法
- 将
i = 0。 - 当
i位于字符串内时，将j = i，并在j位于字符串内且s[j]等于s[i]时，让j向前移动。 - 写出
s[i]；如果j-i大于 1，就将它写成十进制文本。 - 将
i设为j，然后重复。
def compress(s):
parts = []
n = len(s)
i = 0
while i < n:
# Move j to the first index after the run that starts at i
j = i
while j < n and s[j] == s[i]:
j += 1
parts.append(s[i])
if j - i > 1:
parts.append(str(j - i))
i = j
return "".join(parts)
易错点和边界情况
- 只有遇到不同的字母时才写入一段。
aabccc的最后一个ccc后面没有其他内容，所以返回a2b。 - 把计数写成一个字符，例如
'0' + count。这样在计数达到 10 时就会出错：12 个b需要用两个字符12表示。 - 单独的字母后面也写上
1。b应该保留为b，而不是b1。 - 忽略大小写。
zzZZZ应该是z2Z3，而不是z5。 - 像 Java 或 C# 中那样，用
+拼接不可变字符串。每次使用+都会复制当前结果，因此循环的复杂度为O(n²)；请使用字符串构建器。
常见问题3
字符串压缩的时间复杂度是多少？
双指针遍历需要 O(n) 的时间，因为扫描索引只会向前移动。除了结果之外，它还会保留两个索引，因此额外空间为 O(1)。
压缩后的字符串会比原字符串更长吗？
这个版本不会。单独一个字母仍然是一个字符，而连续出现的 k ≥ 2 个字母会变成一个字母加上 k 的数字，长度不会超过 k 个字符。每个字母后都写上计数的方案，例如 a1b1，可能会使长度翻倍。
如何原地压缩字符串？
使用一个字符数组，并设置读取索引和写入索引。用读取索引扫描每个连续段，然后在写入索引处写入该段的字符和长度对应的数字。输出长度不会超过已读取的输入长度，因此写入索引不会超过读取索引。最后返回新的长度。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def compress(s):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "aabccc"
预期输出
"a2bc3"