字符串专题导读

从这一篇开始进入字符串专题。字符串看起来是最"日常"的数据结构，但面试里的字符串题几乎都有一个共同要求：尽量原地修改，空间复杂度 O(1)。这个约束把题目从"会调库函数"变成了"理解底层操作"，也是整个专题的训练重点。

先想清楚：Java 的 String 为什么不能原地改

JDK 8 中 String 内部是一个 private final char[] value；JDK 9 之后改成了 byte[] 加编码标记，但关键点没变——这个数组是 final 的，而且 String 没有暴露任何修改某个下标字符的方法。

String s = "hello";
// s.charAt(0) = 'H';        // 编译不过：String 根本没有这样的 API
s = s.replace('h', 'H');     // 看似修改，实际返回了一个新对象

所有"看起来在改"的方法——concat、replace、substring、trim——都会新建字符串。不可变设计换来了线程安全和常量池复用，但对刷题来说意味着：

想在原串上做双指针交换？先 toCharArray() 转成 char[]。
想一边遍历一边拼接？用 StringBuilder，不要在循环里用 + 拼接 String，每次 + 都产生新对象并复制，复杂度会退化到 O(n²)。

两把趁手的工具

char[]：原地操作的主战场

char[] arr = s.toCharArray();          // 拿到底层副本，可读可写
arr[0] = 'H';                          // 直接改下标
int n = arr.length;                    // 长度固定，适合双指针
String result = new String(arr, 0, n); // 处理完转回去，支持只取前 n 个字符

StringBuilder：动态拼接的首选

StringBuilder sb = new StringBuilder();
sb.append("abc");                 // 尾部追加
sb.append('d');
sb.deleteCharAt(sb.length() - 1); // 删除末尾字符
sb.insert(0, 'x');                // 头部插入（注意是 O(n) 搬移）
sb.reverse();                     // 整体反转
String r = sb.toString();

一个实用认知：StringBuilder 内部维护的也是 char[]。所以"转 char[] 原地处理"和"用 StringBuilder 拼接"经常在同一道题里配合使用——先原地清理，再按需拼接。

别在循环里用 + 拼接 String

String 不可变决定了 + 每次都要新建对象并把旧内容整体复制一遍：

// 反例：循环里用 + 拼接，第 i 次要复制前 i-1 个字符，整体 O(n²)
String r = "";
for (char c : chars) {
    r += c;
}
 
// 正解：StringBuilder 在内部数组上追加，扩容均摊 O(1)，整体 O(n)
StringBuilder sb = new StringBuilder();
for (char c : chars) {
    sb.append(c);
}

面试常问"为什么循环拼接要用 StringBuilder"，答案就藏在不可变性里：这不是语法偏好，而是复制次数的数量级差异。

专题知识地图

整个专题按难度递增可以分成四个板块：

板块	核心技巧	代表题目
反转系列	双指针首尾交换，按规则分组	344、541
原地清理与重组	快慢指针去空格 + 两段式反转	151
替换与旋转	预留空间从后往前填；局部反转 + 整体反转	替换空格/替换数字、右旋字符串（卡码网）
KMP 模式匹配	前缀表（next 数组）	28、459

反转系列：一切的原点

344 反转字符串是最纯的双指针模板，541 在它外面套了一层分组规则：每 2k 个字符一组，只反转每组的前 k 个；剩余部分不足 k 个则全部反转，在 k 到 2k 之间则只反转前 k 个。

s = "abcdefg", k = 2，每 2k = 4 个字符一组：
[ a b c d ] [ e f g ]        分组
  ↑反转前 2    ↑剩 3 个 ≥ k，反转前 2 个
"ba" cd      "fe" g          → 结果 "bacdfeg"

把 reverse(char[], left, right) 这个辅助函数写熟，后面一半的题都在复用它。

原地清理与重组：快慢指针登场

151 翻转字符串里的单词要求去掉多余空格并反转单词顺序，空间 O(1)。它的解法是三步组合：快慢指针原地去空格 → 整体反转 → 逐词反转。"局部反转 + 整体反转"是字符串题的高频套路，下一篇展开。

替换与旋转：换一个视角看数组

替换类题目（把空格换成 %20、把数字换成 number）展示了一个重要思想：先扩容预留空间，再从后往前填充，避免反复搬移。旋转字符串则用"局部反转 + 整体反转"把环形搬移问题变成两次反转。

KMP：专题的压轴

28 和 459 是 KMP 的两块试金石。KMP 的核心不是背代码，而是回答两个问题：前缀表到底记录了什么？失配时为什么那样回退？第三篇会用手推表格 + 代码逐行对应的方式讲清。

专题题单

题号	题名	一句话考点
344	反转字符串	双指针首尾交换，原地反转的母题
541	反转字符串 II	每 2k 个反转前 k 个，分组边界处理
151	翻转字符串里的单词	快慢指针去空格 + 整体反转 + 逐词反转
28	找出字符串中第一个匹配项的下标	KMP 前缀表的标准应用
459	重复的子字符串	用最长相等前后缀判定字符串周期性

写题前的边界清单

字符串题一半的 bug 出在边界，动笔前先过一遍：

空串 "" 和单字符 "a"：反转、KMP、判重复都要能直接通过。
k 大于字符串长度：旋转、分组反转要先取模或截断。
快慢指针清理后的有效长度：最后要按 slow 截取，而不是用原数组长度。
最后一个单词/最后一段没有分隔符：循环要跑到 length 这个"虚拟边界"才算收尾。

学习建议

每道题先自己写一遍，写不出再看解析，重点核对边界：空串、单字符、k 大于串长。
reverse(char[] arr, int left, int right) 练到肌肉记忆，本专题一半的题靠它。
KMP 允许慢一点：先手动推导几组前缀表，再回头看代码，每一步都能对上手推结果才算过关。

参考

代码随想录 · 字符串专题