# 压缩字符串(一)

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-14%2014%3A59%3A33\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E7%AE%80%E5%8D%95\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#简单) [![](https://img.shields.io/static/v1?label=\&message=%E7%89%9B%E5%AE%A2\&color=green\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#牛客) [![](https://img.shields.io/static/v1?label=\&message=%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#滑动窗口) [![](https://img.shields.io/static/v1?label=\&message=%E5%AD%97%E7%AC%A6%E4%B8%B2\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#字符串)

> [压缩字符串(一)\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/c43a0d72d29941c1b65c857d8ac9047e)

**问题简述**

```
利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2bc5a3。
1.如果只有一个字符，1不用写
2.字符串中只包含大小写英文字母（a至z）。
```

**思路：滑动窗口**

* 定义窗口 `[l, r]`（闭区间）；
* 当 `s[l] == s[r]` 时，移动 `r`；否则，添加 `s[l]` 和 `r - l` 到结果，并将 `l` 移动到 `r` 位置，开启下一个窗口；
* 注意最后一个窗口，`r` 的循环区间应该是 `[0, N]`，而不是 `[0, N-1]`，所以在判断 `s[l] == s[r]` 时要注意边界；

<details>

<summary><strong>Python</strong></summary>

```python
class Solution:
    def compressString(self , s ):
        if not s: return ''
        
        N = len(s)
        ret = []
        
        l, r = 0, 0
        while r <= N:  # r 需要遍历到最后一个字符的下一个位置
            # 当不满足条件时，直接移动 l 到 r，不需要 while 判断
            if r == N or s[l] != s[r]:  # 注意判断顺序
                ret.append(s[l])
                if r > l + 1:
                    ret.append(str(r - l))
                l = r
            r += 1
            
        return ''.join(ret)
```

</details>