P3205. 字符串摘要

解题思路

去除非字母字符

去除非字母字符的操作非常简单，使用以下代码即可完成：

字符摘要规则

每一个字符都会被摘要为 字母 + 数字 的形式。对于每一个字符 ch，分为两种情况：

• 若 ch 属于 连续字母，那么后面的数字应该是本段连续字母的个数
• 若 ch 属于 非连续字母，那么后面的数字应该是该 ch 右边的相同字母的个数

统计连续字母个数

对于第一点，统计某一段连续字母的个数，可以用 滑动窗口 来解决这个问题。

统计右侧相同字母个数

对于第二点，储存每一个字符 ch 右边的相同字母的个数，很容想到用 哈希表 来储存元素个数，但需要 从右往左 遍历字符串 s。

滑动窗口的方向调整

正因为上述问题的存在，所以滑动窗口的过程不再是常规的 right 右移再动 left 右移，而是先令 left 左移再令 right 左移，即构建一个 从右往左 进行的滑动窗口。

滑窗三问

• Q1：对于每一个左指针 left 所指的元素 ch，做什么操作？
• Q2：右指针 right 移动到什么位置？
• Q3：如何进行答案的更新？

滑窗三答

• A1：将其与右指针 right 所指的元素 s[right] 进行比较
• A2：右指针 right 移动到当前左指针 left 的位置，用于后续的继续判断
• A3：右指针 right 所指字母和左指针 left 所指字母不相同时，更新答案

复杂度分析 设原字符串长度为 n。第一步过滤非字母字符（C++ 版同时转小写）遍历一次，O(n)。第二步从右往左的滑窗只扫描一遍字符串：left 从 n-1 走到 0，right 只在字符段切换时跳到 left 的位置，每个字符恰好被比较一次，更新哈希表 dic 是均摊常数操作，这一步 O(n)。第三步对摘要结果 ans 排序，ans 里每个元素对应一段连续字符，段数最多为 n，排序最坏 O(n log n)。所以总时间复杂度 O(n log n)，瓶颈在最后的排序；空间上，过滤后的字符串、哈希表与结果列表合计 O(n)。

边界与注意事项

• 大小写不区分：比较和统计都先转小写，输出也是小写形式，代码里通过 lower() / tolower() 落实。
• 主循环只在当前字符与右指针字符不同时才结算一段，最左边那一段连续字符在循环里永远不会触发结算，所以循环结束后必须再补一次 update（传 left = -1），漏掉这一步会丢失第一段的摘要。
• 非连续字母（段长为 1）输出的数字取自哈希表 dic，含义是该字母之后出现的相同字母总数；连续字母（段长大于 1）输出的数字是本段长度。两种情况结算完都要把本段个数累加进 dic，供更靠左的同字母段查询。
• 排序是双关键字：先按数字降序，数字相同再按字母升序，对应代码中的 key = lambda x: (-x[1], x[0])，两个方向别写反。