先问一个问题如果你拿到一串字符比如aabbbccdd要你把它变成abcd把连续重复的部分压成一个你会怎么处理这个问题看起来小学一年级难度但我在真实的项目里见过太多人把它写复杂了。有人上来就搞哈希表有人先转数组再遍历还有人直接用字符串替换做循环把一个 O(n) 的事做成 O(n²)。更麻烦的是很多人分不清“去重连续字符串”和“去重所有重复字符”——这俩虽然听起来像但处理逻辑完全不同。前者只去掉相邻的重复项banana处理完还是banana后者却会变成ban。今天这篇就把这个需求彻底聊透从算法原理到多语言实现再到 SQL 场景和实战坑位一次性给你讲清楚。1. 问题定义与场景拆解1.1 连续字符串去重到底是什么先给一个严谨的定义给定一个字符串s把其中所有连续出现的相同字符压缩为单个字符即对于任意位置i如果s[i] s[i1]则删去s[i1]重复这个过程直到没有相邻字符相同。用数学点的说法是把字符串中每一段“由同一字符构成的极大连续子串”替换成单个该字符。举个具体例子aabbbccdd→abcdhello world→helo world注意两个l被压缩成一个aaaa→abanana→banana因为没有任何相邻字符相同→a→a很多人会默认“去重”就是“保留第一次出现的字符后面出现的全部删掉”这种理解面对banana时就会出错。如果按“首次出现去重”来做结果会是ban但按“连续去重”来做结果不变。这个区别必须在动手写代码前就先想清楚否则方向错了后面全白做。1.2 典型应用场景不止是算法题这个需求乍看像是面试题或 LeetCode 题但实际开发里碰到它的频率远超想象。我梳理一下我碰过的几类真实场景第一个是日志清洗。服务端日志里经常出现因为网络重传或重复上报导致的连续相同日志行比如ERROR: timeout连续刷了十几遍。做监控报表时通常不关心具体刷了多少次只关心“这个错误出现过”所以要把连续重复的日志行压成一条再统计每类错误出现的次数。第二个是输入归一化。用户输入的文本里有大量连续空格、连续换行比如hello world要变成hello world这本质上就是字符层面的连续去重只不过针对的字符是空格和换行符。第三个是数据迁移与 ETL。我在做数据库清洗时常遇到某个字符串字段因为历史数据拼接问题出现了连续重复的子串比如客户-客户-张三这种脏数据。清洗规则就是先把-的连续重复去掉再做后续拆分。这属于字符串连续去重的子串版本原理是一样的。第四个是协议解析。某些自定义协议里为了防干扰或做对齐会填充连续的空字节或填充字符解析时先做连续去重再提取有效内容。这个场景对性能要求比较高因为数据量大解析窗口短写不好就被调度算法拖垮了。所以别把这个需求当成“面试才用得上”的小技巧一旦你真的遇到了一个干净利落的连续去重算法能省下不少事。2. 算法设计思路与核心原理2.1 遍历法最直观也最容易被低估核心思路极其简单维护一个“上一个字符”的变量从头到尾扫描字符串如果当前字符不等于上一个字符就把它追加到结果中同时更新上一个字符如果相等直接跳过。我用伪码描述一下result prev 空字符或哨兵 for ch in s: if ch ! prev: result ch prev ch # 相等则什么都不做 return result这个算法为什么是对的因为它利用了连续重复的本质——在一段连续的相同字符串里只有第一个字符与它前面的字符不同后面的每个字符都和它前面的字符相同所以只有第一个字符会被保留。这个性质保证了输出结果中不可能出现相邻相同字符同时每一个非首字符都被跳过不会漏掉有效内容。时间复杂度是 O(n)只需要一次完整扫描空间复杂度看实现方式如果用不可变字符串做追加需要 O(n) 额外空间如果用可变字符数组原地操作可以做到 O(1) 额外空间。这个解法已经能覆盖 95% 的真实需求。我后来去面试别人时发现能快速写出遍历法的人不少但能清晰讲出“为什么第一个字符被保留、后面的被跳过”的人很少。这个“为什么”恰恰是面试官最想听的。2.2 原地双指针工程上更优的解法如果要在 C/C 这类可以原地修改字符串的语言里做双指针法是更好的选择。思路是维护两个指针一个慢指针write指向结果中下一个要写入的位置一个快指针read指向当前扫描的字符。当s[read]不等于s[write - 1]时把s[read]写入s[write]write后移否则只移动read。这个算法本质上就是遍历法去掉额外结果数组的版本。好处是内存占用小不需要额外分配一大块空间坏处是你在原地覆盖了原字符串如果后续还需要原始字符串就得先做一次拷贝。我一般在 C 里直接调用std::unique它做的就是这个事。但要注意std::unique会返回新的逻辑结尾迭代器原字符串从新结尾到旧结尾之间的内容并没有被清除只是“逻辑上失效”如果你直接打印整个字符串会看到后面残留了旧的字符。2.3 栈法换一种视角能解决变体问题遍历法处理“保留一个重复字符”很顺手但如果需求变成“把所有连续重复的字符全部删除再继续合并”比如abbbac要变成ac因为bbb全删掉之后a和a相邻又需要合并遍历法就不够用了——因为删除一段字符之后新的相邻关系才会暴露出来。这种场景需要用到栈。栈的思路是遍历每个字符判断当前字符是否与栈顶字符相同。如果相同说明它是重复字符直接跳过如果不同压入栈中。但要注意这只是“相邻重复全部删除”的简化版。真正的完全消除比如 LeetCode 1047 的变体是如果遇到与栈顶相同的字符不仅跳过当前字符还要把栈顶弹出来这样一对重复字符就被“抵消”了。我举个例子abbbac用“保留一个”的栈法a 入栈b 入栈第二个 b 跳过第三个 b 跳过a 入栈c 入栈最终栈内是abac。用“完全消除”的栈法a 入栈b 入栈第二个 b 与栈顶 b 相同弹出栈顶 b第三个 b 再和新的栈顶a比较不同则入栈最终栈内是aac不对让我重新推演。其实“完全消除”要小心处理abbbac字符依次为 a、b、b、b、a、c。a 入栈栈[a]b 入栈栈[a, b]遇到 b和栈顶 b 相同弹出栈顶 b栈[a]遇到 b和栈顶 a 不同入栈栈[a, b]遇到 a和栈顶 b 不同入栈栈[a, b, a]遇到 c入栈栈[a, b, a, c]所以结果是abac。等等我把“完全消除”的规则搞混了。“完全消除”通常意味着只要存在连续相同的字符就全部删掉删除后如果又形成新的相邻相同继续删。比如abbbac先看到bbb全部删除变成aac再看到aa全部删除变成c所以结果是c。这个用栈要怎么做对于“全部删除连续的相同字符”需要计数。栈里存(字符, 连续出现次数)。遇到相同字符就增加计数如果连续出现次数达到预设阈值比如 2就要考虑是否移除。如果不设阈值只是“所有连续重复的都删光”那其实栈里不应该存任何连续相同的字符所以每次遇到和栈顶相同的字符就不入栈而是把栈顶弹出这样正好删掉一对再遇到第三个相同字符时又和新的栈顶比较。我重新模拟一遍a 入栈栈[a]b 入栈栈[a, b]当前 b 与栈顶 b 相同弹出 b栈[a]当前 b 与栈顶 a 不同入栈栈[a, b]当前 a 与栈顶 b 不同入栈栈[a, b, a]当前 c 入栈栈[a, b, a, c]这样结果还是abac不是c。问题出在“第三”这个 b 没有被删除因为它在第二个 b 被弹出后才入栈此时它跟前一个 a 不同所以留下了。这说明“每次遇到相同就弹出栈顶”这个规则只适用于“成对删除”而不是“连续段全部删除”。如果要处理“连续段全部删除”更清晰的做法是先统计每一段连续字符的长度长度大于等于 2 的整段丢弃长度为 1 的保留。这只需要一次遍历分段统计不需要栈的复杂操作。所以我把栈法放进来主要价值是解决变体问题而不是解决标准问题。标准问题用遍历法就足够了。2.4 正则表达式一行搞定但有前提正则法是最“偷懒”的方案在 Python、JavaScript、Java 等语言里都可以用。核心模式是(.)\1表示“任意字符后跟一个或多个相同的字符”然后替换为$1或\1。写出来像这样Pythonre.sub(r(.)\1, r\1, s)JavaScripts.replace(/(.)\1/g, $1)Javas.replaceAll((.)\\1, $1)这个做法的优点是极简可读性也不错熟悉正则的人一眼就能看懂意图。缺点是正则引擎的匹配性能在不同语言里差异很大而且一旦字符集变复杂比如要连续去重的是一个由多个字符组成的子串正则会很快变得难写难维护。所以我的建议是短字符串、对性能不敏感、逻辑简单的场景放心用正则大数据量、日志实时清理、协议解析别用。3. 多语言实操与代码实现3.1 Python三行代码 一个正则Python 的字符串是不可变对象所以最简单的实现就是遍历法。def dedup_consecutive(s: str) - str: if not s: return result [s[0]] for ch in s[1:]: if ch ! result[-1]: result.append(ch) return .join(result)这里用列表而不是字符串做拼接是因为 Python 字符串不可变每做一次都是创建新对象在长字符串场景下性能很差。列表拼接避免了这个问题最后一次性join是 O(n) 的。测试一下test_cases [aabbbccdd, hello world, aaaa, banana, , a] for t in test_cases: print(repr(t), -, repr(dedup_consecutive(t)))运行结果aabbbccdd - abcd hello world - helo world aaaa - a banana - banana - a - a如果项目里允许用正则还可以这样写import re def dedup_with_regex(s: str) - str: return re.sub(r(.)\1, r\1, s)两种方式的结果完全一致。性能方面我用一个 100 万字符的随机字符串做了个简单的非正式测试遍历法大概在 0.1 秒级别正则法在 0.3 秒级别都在可接受范围内。但如果字符串更长或调用频率更高差距会被放大。3.2 JavaStringBuilder 是首选Java 也有StringBuffer和StringBuilder做字符串拼接一定要选StringBuilder因为它非线程安全但性能更好在单线程场景下完全够用。public class DedupConsecutive { public static String dedup(String s) { if (s null || s.isEmpty()) { return ; } StringBuilder sb new StringBuilder(); sb.append(s.charAt(0)); for (int i 1; i s.length(); i) { char c s.charAt(i); if (c ! sb.charAt(sb.length() - 1)) { sb.append(c); } } return sb.toString(); } public static void main(String[] args) { String[] tests {aabbbccdd, hello world, aaaa, banana, , a}; for (String t : tests) { System.out.println(t - dedup(t)); } } }运行结果和 Python 版本一致。这里有一个细节sb.charAt(sb.length() - 1)获取最后一个字符比维护一个prev变量更省心因为prev需要在每次追加后手动更新容易漏。如果想用双指针在原地做可以先把 String 转成 char 数组再操作不过 Java 的字符串本质上不可变转数组已经是一个 O(n) 的拷贝原地优势不明显。所以我更建议直接用 StringBuilder。3.3 C标准库 std::unique 直接用C 标准库里的std::unique算法正是“去重连续重复元素”直接用就是最稳的答案。但要注意std::unique作用于迭代器区间且返回新的逻辑结尾不会真正清除容器中末尾的元素。#include iostream #include string #include algorithm int main() { std::string s aabbbccdd; auto new_end std::unique(s.begin(), s.end()); s.erase(new_end, s.end()); std::cout s std::endl; // abcd return 0; }std::unique的默认行为是对于相邻的重复元素保留第一个把后面的元素前移覆盖。所以aabbbccdd经过 unique 后变成abcddddd逻辑上后几个位置残留了旧值再通过erase把从new_end到end()的残留字符清掉就得到干净的abcd。如果你不想改原字符串也可以传入std::back_inserter配合std::unique_copystd::string s aabbbccdd; std::string result; std::unique_copy(s.begin(), s.end(), std::back_inserter(result)); // result: abcdstd::unique的时间复杂度是 O(n)空间复杂度是 O(1)原地版本是 C 里最省心的方案。用之前记得 includealgorithm和string。3.4 JavaScript正则最顺手reduce 很优雅JavaScript 的字符串不可变和 Python 类似。我平时常用正则一行搞定const dedup (s) s.replace(/(.)\1/g, $1); console.log(dedup(aabbbccdd)); // abcd console.log(dedup(hello world)); // helo world如果不想用正则也可以借助数组的reduceconst dedup (s) [...s].reduce((acc, ch) { if (acc[acc.length - 1] ! ch) { acc ch; } return acc; }, ); console.log(dedup(aabbbccdd)); // abcd注意acc[acc.length - 1]在空字符串时返回undefined所以undefined ! ch恒为真第一个字符一定能被追加进来逻辑是安全的。如果要在浏览器环境或 Node.js 处理超长字符串正则的g全局匹配在部分老版本引擎上会有性能问题我建议用for...of循环加数组避免构建中间数组function dedup(s) { let result ; let prev ; for (const ch of s) { if (ch ! prev) { result ch; prev ch; } } return result; }这个版本在 V8 引擎上压测过100 万字符大约 50ms 左右比正则快不少。3.5 SQL 场景连续重复行怎么去字符串层面的连续去重在 SQL 里对应的是“连续重复行去重”。比如一张日志表同一个错误消息连续出现多行要压缩成一行。假设表结构如下CREATE TABLE log ( id INT PRIMARY KEY, ts DATETIME, message VARCHAR(255) );要删除“message 连续相同”的多余行保留每组连续重复中的第一行可以用窗口函数LAG()来做标记然后删除标记为重复的行。在 MySQL 8.0 或 PostgreSQL 中可以这样写WITH cte AS ( SELECT id, message, LAG(message) OVER (ORDER BY ts, id) AS prev_message FROM log ) DELETE FROM log WHERE id IN ( SELECT id FROM cte WHERE prev_message message );思路是按时间顺序排列每条记录与它上一条的message比较如果相同说明它是连续重复行删除。LAG()窗口函数正好实现“取上一行的值”比用自连接更简洁高效。如果数据库版本不支持窗口函数比如 MySQL 5.7可以用变量模拟SET prev_message NULL; DELETE FROM log WHERE id IN ( SELECT id FROM ( SELECT id, prev_message AS prev_message, prev_message : message AS curr_message FROM log ORDER BY ts, id ) t WHERE prev_message curr_message );这种变量写法读起来有点绕但原理和LAG()一样。核心是理解“连续”这个语义在 SQL 里没有天然的表达方式必须以某个排序键为基础人为构造“上一行”的概念。4. 边界情况、复杂度分析与性能优化4.1 边界情况清单测试用例不能漏写任何算法题或工具函数先列边界用例再写实现是避免隐性 bug 的最好习惯。连续字符串去重的边界用例我一般按下面这张表来覆盖分类输入期望输出说明空字符串不能报错单字符aa不改变全相同aaaaa压缩到极限无重复bananabanana不改变注意与全局去重区别连续重复在开头aaabab开头段压缩连续重复在结尾abbbab结尾段压缩数字与特殊字符1222333!!!123!非字母字符也要处理中文哈哈呵哈呵多字节字符不能拆错空白字符a b两个空格a b空格也是字符换行符a\n\nba\nb换行可见字符处理我特别强调中文和 emoji 的情况。在 Python 3、Java 的 String、C 的 std::string、JavaScript 的for...of中Unicode 码点的处理大体是正确的但如果你用charAtJava或s[i]C按下标访问遇到超过 BMP 的字符比如 emoji可能拿到半个码元导致去重结果错误。稳妥的做法是用语言提供的 Unicode 安全迭代方式比如 Python 的for ch in s、JavaScript 的Array.from(s)或for...of。4.2 时间与空间复杂度别把 O(n) 写成 O(n²)标准遍历法的复杂度很简单时间复杂度O(n)n 是字符串长度。只需扫描一遍。空间复杂度原地版本 O(1)非原地版本 O(n)。但要警惕一个隐藏陷阱在 Python 和 JavaScript 这类不可变字符串语言里如果你用result ch这种方式做拼接语言内部是否每次都复制整个字符串在 Python 的 CPython 实现里对单个字符的有优化某些情况下是原地扩展但 JavaScript 的字符串拼接在不同引擎上表现不一大量拼接时可能退化成 O(n²)。所以我在第 3.1 和 3.4 节特意用了Listjoin、Array或循环方式来规避这个坑。用一段简单的话说明如果你发现一个“看起来 O(n)”的去重代码在处理 10 万以上字符时变得异常慢优先怀疑字符串拼接方式而不是算法本身。4.3 内存优化与“预分配”在 C 和 Java 中如果你明确知道结果不会超过原字符串长度可以考虑预分配容量减少扩容带来的内存拷贝。C 的std::string可以用reservestd::string dedup(const std::string s) { if (s.empty()) return ; std::string result; result.reserve(s.size()); // 最多不会超过原长度 result.push_back(s[0]); for (size_t i 1; i s.size(); i) { if (s[i] ! result.back()) { result.push_back(s[i]); } } return result; }Java 的StringBuilder可以用构造器指定初始容量StringBuilder sb new StringBuilder(s.length());这点在超长字符串场景下收益很直观省掉多次数组扩容的时间。如果你的字符串只有几百个字符那没关系不必特意写这些直接写最简单的版本就好。5. 实际开发中的常见问题与排查技巧5.1 字符编码与 Unicode 踩坑实录我之前在某次清洗用户昵称时就栽过跟头。需求是把用户昵称里连续重复的 emoji 去掉比如开心变成开心。在 Java 里如果用charAt遍历遍历的单位是 UTF-16 的 code unit一个 emoji比如 会被当作两个char处理导致比较出问题遇到两个 emoji 时第一个char相等、第二个char也相等但代码写的逻辑可能只比较了第一个char结果把 emoji 拆成了两半输出了乱码。解决办法就是按 Unicode“码点”遍历。Java 从 8 开始可以用codePoints()方法public static String dedupCodepoints(String s) { StringBuilder sb new StringBuilder(); int prev -1; for (int cp : s.codePoints().toArray()) { if (cp ! prev) { sb.appendCodePoint(cp); prev cp; } } return sb.toString(); }codePoints()返回IntStream每个整数代表一个码点这样 emoji、中文等都不会被拆开。JavaScript 里用for...of也天然安全Python 3 的字符串默认就是 Unicode code point 序列直接遍历就好。这个坑遇到了就是线上事故没遇到就是纸上谈兵。我建议调试任何包含中文、emoji、特殊符号的去重逻辑时先跑一组多语言字符用例。5.2 大小写、空白字符和换行符需求里最容易被忽视的细节“去重连续的字符串”看上去是纯字符比较问题但真实业务里往往会附带额外的归一化要求。比如日志清洗时Error和ERROR在视觉上可能来自同一个错误类型但字符级别它们不相等所以连续去重不会把它们合并。这时候需要先把文本转成统一大小写再做去重。还有空白字符的问题。全角空格U3000和普通空格U0020是不同的字符hello world两个全角空格和hello world两个半角空格在字符层面都不一样。如果你的目标是“把连续空白压成一个空格”那不能只看单个字符而要把“空白字符组”视为一个整体再决定是否保留。这个场景下直接的正则/\s/g替换为单个空格更高效。换行符也要小心Windows 的换行是\r\nLinux 是\n。如果你在 Windows 环境下处理文本line1\r\n\r\nline2里的\r\n是两个字符按字符遍历时你看到的是\r和\n交替出现连续去重不会把它们识别为“同一个字符的重复”自然也不会把连续空行压缩成一行。如果需求是“压缩连续空行”得用专门的正则(?:\\r?\\n){2,}或者先把\r\n统一成\n再处理。这个细节经常导致“本地正常、线上不对”的诡异问题。5.3 性能问题排查几百万字符下的速度对比我帮团队做过一个日志清洗服务输入是一段几百 MB 的文本要对每行进行“连续重复字符压缩”。最初版本用 Java 的String.replaceAll((.)\\1, $1)跑 100 MB 文本要将近 40 秒严重拖慢 ETL 流程。排查步骤先用一个 1 万字符的测试串做基准发现单次调用耗时正常说明问题出在大量调用上。检查正则表达式是否触发了回溯。(.)\1本身是简单的线性匹配理论上不该回溯但replaceAll内部会先编译正则再扫描全串对百万级字符的字符串来说正则编译和匹配开销叠加性能就不乐观。改成手写遍历法后同样的数据量降到不到 5 秒。原因是遍历法只做一次线性扫描没有正则引擎的状态机开销。最终的线上代码长这样简化版public static String dedupFast(String s) { if (s null || s.isEmpty()) return s; StringBuilder sb new StringBuilder(s.length()); sb.append(s.charAt(0)); for (int i 1; i s.length(); i) { char c s.charAt(i); if (c ! sb.charAt(sb.length() - 1)) { sb.append(c); } } return sb.toString(); }从那以后我的原则是小数据量随便用正则代码简洁大数据量尤其超过 1 MB 的字符串老老实实手写线性遍历。这比任何“魔法”都可靠。5.4 常见问题速查表现象可能原因解决办法banana去重后变成ban把“连续去重”误用成“全局去重”理清需求用相邻比较而非哈希表C 用std::unique后字符串尾部有残留unique只返回新结尾不清理尾部用erase(new_end, s.end())Java 处理 emoji 出现乱码用charAt拆分 UTF-16 码元改用codePoints()遍历Python 处理超长字符串速度慢拼接触发反复拷贝改用listjoin正则替换在大文件上很慢正则引擎开销 匹配次数多手写遍历法或改用流式处理SQL 去重把不相邻的重复也删了用了GROUP BY而不是“连续”判断用LAG()窗口函数只比较相邻行压缩连续空行无效\r\n与\n混用先统一换行符再用正则(?:\\r?\\n){2,}5.5 多语言实现速查表语言推荐实现时间复杂度空间复杂度备注Python遍历 list joinO(n)O(n)简单可靠JavaStringBuilder charAtO(n)O(n)大数据量用预分配容量Cstd::unique eraseO(n)O(1)标准库自带最省事JavaScript正则或 for...ofO(n)O(n)emoji 用 for...of 安全SQLLAG() 窗口函数数据库决定数据库决定需要窗口函数支持我个人在实际项目里写这个功能已经形成了固定套路先用最简单的遍历法打底加一组覆盖边界用例的测试如果性能测试表明有问题再考虑正则或原地优化。千万别一上来就上最优解——因为你可能连需求是不是“连续去重”都没确认清楚白白写一堆复杂逻辑。最后再分享一个小技巧调试去重逻辑时不要打印完整的长字符串而是打印“字符 出现次数”的摘要。比如把aaabbbccdd转成[(a,3), (b,3), (c,2), (d,2)]你一眼就能看出哪些地方被压缩了、哪些地方漏了比盯着长字符串硬核对高效得多。这也是我跟一个做数据清洗的老同事学到的后来用这个方法排查过好几次线上问题省了大量时间。