字符串算法刷题指南：双指针、滑动窗口与哈希计数核心模型详解

字符串题在力扣里的占比一直都不低，翻开热题 100 和剑指 Offer，随便就能数出几十道。我早期刷题最怕碰到字符串，因为总觉得它变化多端：有的题考基础 API，有的题考双指针，有的题一上来就要上 KMP、动态规划，光是边界条件就够喝一壶。但刷到后面我才发现，字符串题其实是最有套路可循的一类题，核心就那几个模型，练熟之后反而比链表、树更容易拿分。

这篇文章就从我自己的刷题经验出发，把力扣上字符串相关的经典题目拆开讲一遍，包括双指针、哈希计数、滑动窗口、回文、匹配这几个高频方向，也会把我踩过的坑和刷题顺序建议一起整理出来。适合刚开始刷力扣、想在字符串题上建立体系的新手，也适合刷过一些题但总在边界条件上翻车的老选手。

1. 字符串题目为什么值得单独拆开讲

1.1 字符串题在面试和笔试中的出镜率

先看数据。力扣热题 100 里，字符串相关的题目占了差不多四分之一，不管你是准备校招还是社招，这套题都是绕不开的。而很多公司的技术面试，手写代码环节尤其喜欢出字符串题，原因很简单——字符串题能在一道题里同时考察编码基本功、边界处理能力和算法模型识别能力，一行代码里就塞满了细节。

有些人觉得字符串题不就是调用一下 API 吗？截个串、找个子串、反转一下，有什么难的。但真到了面试手写代码的时候，你会发现字符串 API 的花活根本救不了你，因为面试官考的是你能不能在不依赖高级 API 的情况下，用最基本的数组操作把问题解决。这也解释了为什么力扣上字符串题从简单到困难跨度极大，同一个方向能出出十几种变形。

字符串另一个特点是对语言特性极其敏感。同样是反转字符串，C++ 里可以直接操作 string，Java 需要转成 char[]，Python 用切片一步到位。这种差异不但影响代码写法，还影响时间复杂度和内存占用，所以刷字符串题必须对语言本身的字符串实现有足够了解，这就是我把它单独拉出来讲的原因。

1.2 字符串题真正的三个难点

第一点是字符串的不可变性。除了 C++ 的 string，Java 和 Python 的字符串默认都是不可变对象，每次拼接、替换、插入都会生成新的字符串对象。如果刷题时没注意这一点，很容易写出 O(n^2) 甚至更差的代码，测试用例一长就超时。

第二点是边界条件特别多。空字符串、单字符、全是空格、首尾带空格、大小写混排、数字符号混在一起、超长字符串，这些情况一旦考虑不周，就会出现数组越界、死循环、答案错误。力扣上很多字符串题第一次提交不过，不是因为算法想错了，而是因为边界用例没有照顾到。

第三点是模型识别难。字符串题表面看起来都差不多，实际上底层可能考的是双指针、滑动窗口、哈希计数、回溯、动态规划、KMP 匹配，看不出考点就无从下手。比如同样是“子串”两个字，“无重复字符的最长子串”考滑动窗口，“最小覆盖子串”也是滑动窗口，但“最长回文子串”考的是中心扩展或动态规划，完全不是一个思路。

1.3 字符串题的核心解题模型总览

我把字符串题按底层模型归纳成了六类，先列个总表，后面再逐个展开：

这六个模型基本覆盖了力扣上八成以上的字符串题，剩下两成是数学计算、栈模拟等混合型题目。掌握了这些模型之后，刷题时的状态会从“这题没见过”变成“这题能套哪个模型”，本质上是给自己装了一个问题分类器。

2. 核心细节：字符串处理的基础功

2.1 不可变字符串与可变字符数组

先说一个最基础但也最容易被忽略的点：不同语言里字符串到底能不能原地修改。C++ 的 std::string 是可变的，你可以直接写 s[i] = 'a'，也能对 string 调用 reverse、sort 这类算法；但 Java 的 String 和 Python 的 str 都是不可变对象，一旦创建就不能修改其中的某个字符。

这就带来一个实际的刷题差异。比如“反转字符串”这道题，要求不使用额外空间原地修改输入数组，在 C++ 里可以直接用 swap 操作 string 或 vector<char>；在 Java 里如果输入是 String，就必须先转成 char[]，操作完再转回来；在 Python 里字符串不能原地改，要么用 list(s) 转成列表再反转，要么用切片 s[::-1] 生成新字符串。很多新手在 Java 或 Python 下写反转题，第一反应是直接操作字符串，结果发现编辑器直接报错，就是因为没理解不可变性。

频繁拼接字符串是另一个重灾区。Java 里循环中用 + 拼接字符串，每拼一次都会生成新的 String 对象，循环 n 次就是 O(n^2) 的时间和 O(n) 的额外内存，数据量大一点直接 TLE 和内存爆掉。正确做法是用 StringBuilder 或 StringBuffer。Python 里也一样，频繁拼接用 "".join(list)，不要用 +=。C++ 的 string += 在 capacity 足够时开销不大，但如果反复扩容也会有性能损耗，所以大循环里最好先 reserve 一下容量再拼接。

2.2 C++ 里字符串的几种存储形态

C++ 里字符串有三种常见存储形态：std::string、char 数组、const char* 指针。很多刷题新手被这三种形态绕晕，看到题目里的参数是 string，底层却要求你用 C 风格字符串的思维去处理，非常容易踩坑。

std::string 是 C++ 标准库的字符串类，自带 size()、length()、substr()、find() 等方法，内存自动管理，刷题首选它。char s[] 是字符数组，长度必须包含结尾的 '\0'，比如 char s[] = "abc" 实际占用 4 个字节。const char* p 是字符串字面量的指针，它指向常量区的数据，不能通过 p 修改内容。

字符串数组的初始化也有讲究。定义 string 数组可以这样写：string arr[] = {"hello", "world"};，定义指针数组存放字符串可以写：const char* arr[] = {"hello", "world"};。两者看起来差不多，实际上差别很大：string 数组里每个元素都是完整的 string 对象，有独立的生命周期；指针数组里每个元素只保存了字符串首地址，真正的字符串字面量存放在常量区，如果用 char* 接收那就不能修改内容，用 const char* 才是安全的。

这个细节在嵌入式或者底层开发中特别常见，比如跨任务传递字符串时，很多人直接传一个 char* 指针出去，但接收方不知道这块内存什么时候被释放，就会产生悬垂指针。刷力扣的题虽然不涉及这些工程场景，但理解 char* 和 string 的区别能帮你更好地理解题目输入参数到底是哪一种，排查越界问题时也更有方向。

2.3 常用 API 速查清单

字符串题的很多解法都是常用 API 的组合，把这些 API 背熟能省下大量试错时间。我整理了一份平时常用的清单，不同语言各有差异，刷题时直接对照着用：

这里有几个特别容易踩的坑。C++ 的 s.length() 返回的是无符号数 size_t，如果直接和负数比较，负数会先转成一个巨大的无符号数，条件判断结果完全相反。我之前写过 while (i < s.length() - 1) 这样的代码，当 s 为空时 s.length() - 1 会变成无符号数下溢，直接导致死循环，后来统一改用 int n = s.length() 先存一下再比较才安稳。

Java 的 substring 在 JDK 7u6 之前是 O(1) 返回原字符串的视图，之后变成了 O(n) 拷贝，所以在循环里频繁截取子串也会产生 O(n^2) 的开销。Python 的切片同样是 O(n) 复制，不要以为写起来简单就随便用。理解了这些 API 背后的实现，写出来的代码才不会在复杂度的坑里反复打转。

3. 经典题目实操：双指针、哈希与滑动窗口

3.1 反转字符串：双指针入门模型

力扣 344 反转字符串是一道不能再基础的题，直接给字符数组，要求原地反转。解法就是双指针一头一尾往中间走，交换对应位置的字符，直到两个指针相遇。代码几行就写完：

void reverseString(vector<char>& s) { int left = 0, right = s.size() - 1; while (left < right) { swap(s[left], s[right]); left++; right--; } }

复杂度是 O(n) 时间、O(1) 额外空间，干净利落。这道题的变体“反转字符串中的单词”LeetCode 151 就要多绕一个弯了，它要求把句子里的单词顺序反转，但单词内部的字母顺序不变，同时还要把多余空格去掉。

我在拿到这种题时第一反应是：先把整个字符串反转一次，这样所有单词的顺序反过来了，但每个单词内部也是反的；然后再对每个单词做一次局部反转，单词内部就恢复正常了。这个思路很经典，能在 O(1) 额外空间下解决，实现时还需要额外处理空格。C++ 代码如下：

string reverseWords(string s) { reverse(s.begin(), s.end()); int n = s.size(); int idx = 0; for (int i = 0; i < n; i++) { if (s[i] != ' ') { if (idx != 0) s[idx++] = ' '; int j = i; while (j < n && s[j] != ' ') { s[idx++] = s[j]; j++; } reverse(s.begin() + idx - (j - i), s.begin() + idx); i = j; } } s.resize(idx); return s; }

这里的 idx 是写入指针，它原地覆盖原字符串，同时把多余空格剔除掉。每次写入一个单词后，对这段区间做局部反转，就能把单词内部恢复成正确顺序。整个算法时间 O(n)，额外空间 O(1)。如果你在做笔试而不是大厂手撕，也可以直接用 split 分割后拼接，但面试时能写出这个原地版本会加分不少。

3.2 无重复字符的最长子串：一套滑动窗口模板打天下

LeetCode 3 是字符串题里出镜率极高的一道：给定一个字符串 s，找出其中不含重复字符的最长子串长度。这道题能进热题 100 是有原因的，因为它把滑动窗口这个高频模型的模板完整地演示了一遍。

核心思路是维护一个左指针和一个右指针，右指针不断向右扩展，用一个哈希表记录窗口内每个字符最近出现的位置。当右指针遇到一个已经在窗口内的字符时，左指针需要跳到上一次出现位置的下一个位置，跳过重复字符。这里有个细节是 left 要用 max 更新，因为 left 可能已经被其他字符推得更远了：

int lengthOfLongestSubstring(string s) { unordered_map<char, int> last; int left = 0, ans = 0; for (int right = 0; right < s.size(); right++) { if (last.count(s[right])) { left = max(left, last[s[right]] + 1); } last[s[right]] = right; ans = max(ans, right - left + 1); } return ans; }

这个模板可以套用到很多字符串子串问题。比如 LeetCode 567 字符串的排列，判断 s2 中是否包含 s1 的某个排列，套路上是固定窗口大小等于 s1 的长度，维护两个哈希表比较字符频次。再看 LeetCode 438 找到字符串中所有字母异位词，同样是固定窗口滑动，把每个窗口的字符频次和 p 的频次比较。

还有一类题目的条件复杂一些，比如给定一个只包含 r、g、b 三种字符的字符串 s，求长度为 m 的子串中有多少个满足某种颜色数量条件。这种题本质上就是固定窗口 + 计数，窗口向右滑动时更新三种字符的数量，每次滑动后检查条件。只要把滑动窗口模板写熟，这类题都能十分钟内拿下。

3.3 字母异位词分组：排序与哈希的配合

LeetCode 49 字母异位词分组，输入是若干单词，要求把由相同字母组成的单词归到一组。比如 ["eat", "tea", "tan", "ate", "nat", "bat"]，eat、tea、ate 就是一组。

最直观的做法是：把每个单词按字母排序，排序结果相同的单词就是同一组。用排序后的字符串作为 key，原字符串作为 value 存入哈希表，最后把所有 value 收集起来就是答案。C++ 实现如下：

vector<vector<string>> groupAnagrams(vector<string>& strs) { unordered_map<string, vector<string>> mp; for (string& s : strs) { string key = s; sort(key.begin(), key.end()); mp[key].push_back(s); } vector<vector<string>> res; for (auto& p : mp) res.push_back(p.second); return res; }

这个解法的时间复杂度是 O(nklogk)，n 是字符串数量，k 是单个字符串的最大长度。力扣上很多字符串排序相关的题目走的都是这个路子，比如判断两个字符串是否互为字母异位词 LeetCode 242，直接排序后比较即可。

如果想优化到 O(nk)，可以把排序换成计数数组生成 key。比如用一个长度为 26 的数组统计每个字母出现次数，然后拼成一个字符串作为哈希键。这个方案在面试中讲出来会比排序更亮眼，因为时间复杂度和哈希键的信息量都更优。要注意的是，有些题目要求忽略字母大小写来比较，那就先把字符统一转成小写或者大写再生成 key，这一步很多新手会漏掉。

字符串排序本身也是热点考点，比如 LeetCode 451 根据字符出现频率排序，把字符串按字符出现频率降序重新排列。这类题背后的逻辑就是“统计频次 + 排序 + 重新拼接”，掌握哈希计数的基本盘之后，变化再多也能应对。

3.4 字符串转整数：边界处理是最大的坑

LeetCode 8 字符串转换整数是我早期刷题时最强的一道，它不讲什么高深算法，纯粹考你边界处理做得到不到位。题目要求实现一个类似 atoi 的函数：跳过前导空格，处理正负号，读取连续数字，遇到非数字字符停止，数字溢出时返回 INT_MAX 或 INT_MIN。

这题最容易翻车的点就是溢出判断。我最早写的是 num 用 int 保存，每次 num = num * 10 + digit 之前先判断是否超过 INT_MAX / 10，判断逻辑一错答案就崩。后来为了保险，直接用 long long 存，循环里判断超过 INT_MAX 就提前返回，代码反而更好写：

int myAtoi(string s) { int i = 0, n = s.size(); while (i < n && s[i] == ' ') i++; int sign = 1; if (i < n && (s[i] == '+' || s[i] == '-')) { sign = (s[i] == '-') ? -1 : 1; i++; } long long num = 0; while (i < n && isdigit(s[i])) { num = num * 10 + (s[i] - '0'); if (num * sign > INT_MAX) return INT_MAX; if (num * sign < INT_MIN) return INT_MIN; i++; } return (int)(num * sign); }

这里有几个点值得注意。isdigit 要包含头文件 <cctype>，但力扣环境通常已经引入。空字符串、只有正负号、正负号后面没有数字、数字中间夹着其他字符、首字符就是非数字字符，这些情况都要在测试时单独验证。

字符串转数字这种操作在真实业务里也比比皆是，数据库里的日期字符串转日期格式、配置文件里的数字串解析、用户输入的数字校验，核心都是同一个问题：先清理空白，再判断符号，再逐位转换，同时处理异常。刷这道题时积累的边界处理经验，落到实际工作中非常实用。

4. 进阶题型的处理套路

4.1 回文串系列：中心扩展和双向删除

回文串在字符串题里是一大门类。LeetCode 5 最长回文子串是经典中的经典，给定一个字符串，返回其中最长的回文子串。解法有多重：动态规划 O(n^2)、中心扩展 O(n^2)、Manacher 算法 O(n)。面试最常考察的是中心扩展法，思路很朴素：回文串是关于中心对称的，我们枚举每个可能的中心位置，向两边扩展，直到两侧字符不同为止。

中心有两种情况：一个字符作为中心，对应奇数长度回文；两个相邻字符共同作为中心，对应偶数长度回文。所以枚举时要同时检查这两种中心。C++ 核心代码如下：

string longestPalindrome(string s) { int n = s.size(); int start = 0, maxLen = 0; auto expand = [&](int left, int right) { while (left >= 0 && right < n && s[left] == s[right]) { left--; right++; } return right - left - 1; }; for (int i = 0; i < n; i++) { int len1 = expand(i, i); int len2 = expand(i, i + 1); int len = max(len1, len2); if (len > maxLen) { maxLen = len; start = i - (len - 1) / 2; } } return s.substr(start, maxLen); }

扩展函数返回的是实际回文长度，因为退出循环时 left 和 right 分别多走了一位。中心扩展的时间复杂度是 O(n^2)，空间 O(1)，对一般面试题已经完全够用。Manacher 虽然能做到 O(n)，但实现复杂度高，如果不是专门钻研这类题，可以放到后面再学。

回文串还有一个很常见的变形：“给定一个仅由小写英文字母组成的字符串 s，找出所有删除该位置字符后能使剩余字符串成为回文串的位置”。这种题典型的思路是：先用双指针从两端往中间比较，如果发现左右字符不相等，那么只需要考虑删除左边那个字符或右边那个字符，然后检查剩余部分是否为回文。LeetCode 680 验证回文串 II 就是“判断能否通过删除一个字符变成回文串”的版本，把思路改一下就能处理“返回布尔值”而不是“找出所有位置”的变体。

在 n 比较小的前提下，“找出所有位置”可以朴素一点：枚举每个位置 i，删除它，然后用双指针判断剩余字符串是否回文，时间复杂度 O(n^2)，n 在几百以内完全可行。如果 n 很大，就要结合前缀和或者 Manacher 预处理优化，这种题更多出现在竞赛里，笔试很少考到，先把朴素思路吃透最重要。

4.2 字符串匹配：KMP 到底要不要背

LeetCode 28 实现 strStr()，也就是找出模式串在文本串中第一次出现的位置，这类问题在字符串题里属于老牌考点。最简单的解法是双循环暴力匹配，外层遍历文本串，内层对每一个位置尝试匹配模式串，时间复杂度 O(n*m)。数据量小的时候完全够用，但面试官一般会追问：能不能优化？

这时候就得搬出 KMP 算法。KMP 的核心是 next 数组，也叫前缀函数，它记录了模式串中每个前缀的最长相等前后缀长度。当匹配失败时，不需要从头开始匹配，而是根据 next 数组把模式串向右滑动一大段，从而把时间复杂度降到 O(n+m)。

next 数组的构建是理解 KMP 的关键。以模式串 “ababc” 为例，它的前缀函数在位置 4 的值是 2，表示前缀 “abab” 的最长相等前后缀是长度为 2 的 “ab”。匹配失败时，模式串指针回退到 j = next[j - 1]，文本串指针不需要回退，这就是 KMP 高效的根本原因。手写 KMP 的代码量大概三十行，面试前最好能默写一遍，因为很多面试官就喜欢考这种“基础但有点门槛”的算法。

但我也要说句实话：在实际刷题和笔试中，如果你的目标是快速 AC，直接用语言内置的查找函数更稳妥。C++ 的 s.find(sub)，Java 的 indexOf，Python 的 s.find(sub) 都能直接解决这道题。KMP 的真正价值在于理解字符串匹配的底层原理，以及面对“找最小重复子串”、“判断字符串是否由某个子串循环构成”这类变体题时，你能立刻想到用前缀函数解决。所以我的建议是：原理必须懂，模板可以备着，但不要无脑背。

4.3 分割与回溯：全排列思想在字符串题里的应用

字符串题里还有一大类是分割和组合，典型代表是 LeetCode 131 分割回文串和 LeetCode 17 电话号码的字母组合。这类题底层全是回溯算法，模板化很高，掌握了套路之后一通百通。

以 131 分割回文串为例：给定字符串 s，要求把所有可能的分割方式都输出，且每个分割后的子串都是回文串。思路是 DFS 从左到右扫描，枚举从当前位置开始的所有可能子串，如果子串是回文串，就加入路径，然后继续递归处理剩余部分。每次递归结束后回溯，弹出最后一个元素。C++ 代码如下：

vector<vector<string>> partition(string s) { vector<vector<string>> res; vector<string> path; function<void(int)> dfs = [&](int start) { if (start == s.size()) { res.push_back(path); return; } for (int end = start; end < s.size(); end++) { if (isPalindrome(s, start, end)) { path.push_back(s.substr(start, end - start + 1)); dfs(end + 1); path.pop_back(); } } }; dfs(0); return res; }

isPalindrome 函数就是双指针判断子串是否回文，代码简单，不另写了。这类回溯题的共同特点是：递归处理子问题、路径记录、剪枝，跟求全排列、组合的模板几乎一模一样。我在刷完 131 之后，再做 17 电话号码的字母组合就顺手多了，因为它的 DFS 框架完全一样，只是每一层可选择字符集不同。

在实际工程中，字符串分割也是高频操作。比如解析 URL 参数、处理模板字符串、CSV 解析，全都要用分割加判断。力扣上的分割题练好了，回到业务里写解析逻辑会顺手很多，这也是我建议大家不要跳过回溯专题的原因。

5. 常见问题与排查技巧实录

5.1 超时问题：暴力解法什么时候不可行

字符串题最容易踩的高空陷阱就是复杂度爆表。我见过不少人做“无重复字符的最长子串”时，三重循环枚举所有子串再判重，等提交才发现超时。判断暴力解法可不可行，第一件事是看数据规模：如果 n 在 10^5 量级，O(n^2) 基本必挂，必须想 O(n) 或 O(nlogn) 的解法；如果 n 只有 100，暴力反而往往是最不易出错的方案。

循环内拼接字符串是另一个隐性的高复杂度来源。比如在 for 循环里写res = s[i] + res，每次都是 O(n) 的拷贝，整体 O(n^2)，数据一大就炸。正确做法是先把字符收集到 vector 或 list，最后再一次性拼接成字符串。刷题的时候如果遇到 TLE，先别急着换算法，检查一下代码里有没有在循环里做字符串拼接、substring、replace 这类 O(n) 操作，很多时候改掉这几点就能直接 AC。

滑动窗口和双指针的核心价值就在于把 O(n^2) 的暴力降成 O(n)，它们不是靠什么高深数学公式，而是靠“复用前一次的计算结果”，不让重复的信息白白丢弃。能用哈希和双指针解决的问题，尽量不要写嵌套循环去暴力重算。

5.2 边界条件：空串、全同字符、超大输入

字符串题里 80% 的提交失败都和边界条件有关。我总结了一份自查清单，每次写完代码先拿这些用例过一遍，能省下不少提交次数：

• 空字符串，处理函数会不会越界。
• 只包含一个字符的字符串。
• 所有字符都相同的长字符串，比如 “aaaaaa”。
• 首尾带空格的句子。
• 全部由空格组成的字符串。
• 大小写字母同时存在，且相同字母的大小写互为干扰。
• 包含数字、符号、字母的混合串。
• 字符串长度刚好达到题目上限的超长输入，检查会不会超时或溢出。
• 数字转换题的正负数边界，比如 “-2147483648” 和 “2147483648”。

一个我印象很深的例子是“反转字符串中的单词”，很多解法在全部是空格时会出错，因为有的实现会对空字符串取 s.size() - 1，得到无符号数下溢。类似这种问题，用 int 显式保存长度可以避免大部分坑。养成写完代码先跑边界用例的习惯，比多刷十道题都管用。

5.3 语言差异的坑

每个语言在字符串题上都有自己的脾气。C++ 里 char* 和 string 混用容易踩到 '\0' 截断的问题，网上一搜“C 语言输入字符串输出二维码图像例程”这类问题你就会发现，根源都是没有正确理解字符串结尾标志。Java 里 String 的不可变性、substring 的拷贝，加上常量池的比较陷阱，写起来要格外小心。Python 虽然语法简单，但切片复制、join 的用法都要习惯，不然很容易写出隐式 O(n^2) 的代码。

还有一个容易被忽视的问题：字符串比较的大小写敏感性。力扣的算法题默认比较是区分大小写的，但真实业务中很多数据库默认不区分大小写，比如某些库的字符串模式查询，你查大写字母它可能也会匹配小写字母。另外，数据库里的空值 NULL 和空字符串 '' 是两回事，用 <> 或 != 去过滤空字符串时，NULL 值往往不会被查出来，这个坑在 Oracle 和 MySQL 里都特别常见。算法题里虽然没有这些数据库语义，但理解 size 为 0 的字符串和不存在字符串的区别，对写对边界判断很有帮助。

语言差异造成的 bug 往往比算法思路错误更隐蔽，因为它们不会报错，只是结果不对。排查这种问题没有捷径，只能靠多写多踩坑，把常见的语言陷阱记成自己的笔记。

5.4 力扣刷题顺序建议

很多人拿到力扣热题 100 就从头开始刷，刷几道链表题就放弃了。刷字符串题其实可以按模型分类，逐个击破，效率高很多。我按自己的经验整理了一个推荐顺序，你可以照着练：

重点提醒：第一阶段千万别跳，别看它简单，很多人在 541 反转字符串 II 里就会因为边界条件卡住。第二阶段的滑动窗口是字符串题的重中之重，一定要做到不看题解也能默写模板。第三阶段的哈希题是性价比最高的，面试命中率极高。第五阶段对新手来说可以放缓，先把前四个阶段吃透，字符串题就已经能超过大多数人了。

说点我个人体会。我刷字符串题半年多，最大的感悟是不要一开始就背模板，要先学会把乱糟糟的题目翻译成熟悉的模型。看到“最长子串”想到滑动窗口，看到“反转”想到双指针，看到“异位词”想到哈希计数。每刷一道题，把它的边界条件记进笔记，下次再碰到同类题就能少踩一半坑。字符串题是真的刷一道顶一道，模型识别能力上来了，后面就是流水线操作。