这道题我在本地跑了三遍才真正看懂。标题里那个uniqueLetterString看起来只是返回一个整数但第一次动手时我用的是 O(n^3) 暴力枚举结果连样例都跑得吃力。后来我尝试把问题丢给 DeepSeek让它和我一起拆LeetCode 828才算把“统计子串中唯一的字符”这个题目彻底吃透。今天这篇就围绕这道题讲讲题意背后的坑、贡献法为什么是正解、代码怎么写以及我拿 AI 辅助刷题时总结出的一套提问方法。如果你也卡在“为什么直接枚举子串会超时”“别人代码里那两个数组到底在干嘛”那这篇就是为你准备的。新人能看懂每一步推导刷题老手也能从我踩过的边界问题里捞到点东西。1. 题意拆解先别急着写代码把“唯一字符”四个字读透1.1 从 countUniqueChars 的定义说起LeetCode 828的核心是给定一个字符串s要求所有非空子串的countUniqueChars之和。函数名虽然叫uniqueLetterString但真正的难点在countUniqueChars(t)的定义上它统计的是子串t中出现次数恰好为 1 的字符个数不是“有多少种不同的字符”。很多人的第一反应是算“不同字符数”这俩概念在绝大多数例子里结果一样但一旦出现重复字符就立刻分叉。我举个例子子串ABA按“不同字符数”算结果是 2因为 A 和 B 两种字符都出现过按“出现恰好一次”算结果只有 1因为 A 出现了两次不贡献B 出现了一次贡献 1。别小看这个区别官方样例里s ABA的答案是 8。如果你按“不同字符数”去写算出来会是 10 或者别的数直接错。所以做题第一步不是开编辑器而是把countUniqueChars的定义写在草稿纸最上面提醒自己只有孤零零出现一次的那个字符才值得被统计。1.2 手推一个例子把暴力法的成本看清楚拿题目里经典的s ABA来手动枚举所有子串感受一下过程子串countUniqueChars恰好出现一次结果AA 出现一次1BB 出现一次1AA 出现一次1ABA 一次B 一次2BAB 一次A 一次2ABAA 两次不贡献B 一次1合计是 111221 8。这个过程太直观了所以很多人第一版代码就是三层循环枚举左边界、枚举右边界、统计当前子串里每个字符的频率。我第一版也是这么写的顺手把s换成LEETCODE本地跑完样例输出 92感觉稳了。但问题来了如果n是 10^5三层循环就是 10^15 次操作神仙也救不回来。更麻烦的是每次统计频率还要额外遍历一遍子串实际成本比理论还高。所以必须在“枚举子串”这个思路上彻底转弯不然永远是 O(n^3) 的命。2. 核心思路贡献法把“枚举子串”变成“枚举字符”2.1 为什么每个出现位置可以独立算贡献暴力法之所以慢是因为它在枚举“子串”这个整体而countUniqueChars本质上是把每个字符的贡献加在一起。那么换个角度直接问每个字符的每一次出现它能在多少个合法的子串里当上“唯一一次出现”的那个字符一个字符在某个子串里算作“唯一字符”需要同时满足两个条件这个子串必须包含当前这个出现位置这个子串内不能再出现和当前字符相同的其他字符。也就是说如果我在s里固定某个位置i上的字符c那么真正能决定它贡献多少的是c在i左边最近一次出现的位置prev[i]以及右边最近一次出现的位置next[i]。再直白一点如果某次出现位置左右都被相同字符夹住了那它无论如何都没法成为“唯一”。只有当子串的左边界落在prev[i] 1到i之间右边界落在i到next[i] - 1之间这个出现位置才会在子串里只出现一次。这样的左边界有i - prev[i]种选法右边界有next[i] - i种选法因为左右边界选择互相独立所以贡献就是两者的乘积。2.2 左右边界区间就是子串选择范围用ABA来验证一下这个公式。三个位置分别是 0(A)、1(B)、2(A)。位置 0 的 A左边没有 A记prev -1右边最近的 A 在位置 2记next 2。贡献是(0 - (-1)) * (2 - 0) 1 * 2 2。解释左边界只能选 0右边界可以选 0 或 1对应子串A和AB这两种情况下位置 0 的 A 都是唯一的。位置 1 的 B左边没有 Bprev -1右边没有 Bnext 3。贡献是(1 - (-1)) * (3 - 1) 2 * 2 4。对应左边界可选 0、1右边界可选 1、2组合出四个子串AB、B、ABA、BAB 在里面全是唯一的。位置 2 的 A左边最近的 A 在 0prev 0右边没有 Anext 3。贡献是(2 - 0) * (3 - 2) 2 * 1 2。对应子串A和BA。三个位置贡献加起来242 8和手动枚举完全一致。这就是贡献法的漂亮之处我们不再关心子串长什么样只关心每个字符出现位置在左右同字符之间的“自由活动范围”。这个思路在字符串题里太常见了凡是“统计子串中某种性质之和”的题优先考虑能不能拆成每个位置/每个元素的独立贡献。一旦能拆O(n^2) 变 O(n) 就是顺手的事。3. 代码实现两种我实测好用的写法3.1 用 pre 和 next 数组一次遍历预处理既然要快速拿到每个位置左右最近的同字符位置最朴素的方法就是预处理两个数组prev和next。我先把代码贴出来再逐行解释。class Solution { public int uniqueLetterString(String s) { int n s.length(); int[] prev new int[n]; int[] next new int[n]; int[] last new int[26]; // 预处理 prev Arrays.fill(last, -1); for (int i 0; i n; i) { int c s.charAt(i) - A; prev[i] last[c]; last[c] i; } // 预处理 next Arrays.fill(last, n); for (int i n - 1; i 0; i--) { int c s.charAt(i) - A; next[i] last[c]; last[c] i; } // 累加每个位置的贡献 int ans 0; for (int i 0; i n; i) { ans (i - prev[i]) * (next[i] - i); } return ans; } }先说prev。我用last数组记录每个字符最近一次出现的位置初始都设为 -1表示“还没出现过”。从左往右扫每到一个位置i先把last[当前字符]存进prev[i]再把last更新成i。这样prev[i]就是左边最近同样字符的下标不存在就是 -1。next就是反过来。从右往左扫last初始化为 n表示“右边不存在”。每到一个位置i把last[当前字符]存进next[i]再更新last。这里 n 可以理解为“虚拟的右边越界位置”因为这个位置不属于字符串但右边界可以选到 n-1所以用 n 参与计算时next[i] - i依然能正确表示可选的右边界数量。最后就是累加(i - prev[i]) * (next[i] - i)。这个表达式不需要判断字符是否重复因为即使当前位置只有一个同字符公式也会把它自动处理正确。注意原题字符串限定只有大写英文字母所以last数组大小开 26。如果面试官把范围扩大到 ASCII 可打印字符直接把 26 改成 128 或者用 HashMap 就完事别在这上面栽跟头。3.2 用出现位置列表的写法代码更短prev/next数组的思路非常直白但还有另一种我更喜欢的方式把每个字符的所有出现位置存成列表然后对每个字符的相邻出现位置做区间乘法。class Solution { public int uniqueLetterString(String s) { int n s.length(); ListInteger[] pos new List[26]; for (int i 0; i 26; i) { pos[i] new ArrayList(); } for (int i 0; i n; i) { pos[s.charAt(i) - A].add(i); } int ans 0; for (ListInteger list : pos) { for (int j 0; j list.size(); j) { int p list.get(j); int left (j 0) ? -1 : list.get(j - 1); int right (j list.size() - 1) ? n : list.get(j 1); ans (p - left) * (right - p); } } return ans; } }这个写法的核心是位置列表。比如s ABCA字符 A 的位置列表是[0, 3]。列表里第一个元素 0 的左边用 -1右边用下一个元素 3第二个元素 3 的左边用前一个元素 0右边用 n。这样每个元素的贡献都能单独算逻辑比prev/next数组更集中。两种写法复杂度一模一样都是 O(n) 时间和 O(n) 空间。区别在于prev/next适合现场手撕、容易解释位置列表适合看完思路后快速写对少维护两个数组。我个人更喜欢第二种因为一旦遇到变体题位置列表往往更容易改。3.3 复杂度与返回值细节时间复杂度上无论是预处理还是最终累加都只用了一层循环所以是 O(n)。空间复杂度主要看数组长度prev、next各 O(n)last是常数整体 O(n)。到这一步你已经能 AC 了。但有两点需要额外留心答案要不要取模我搜过讨论区原题的测试数据保证答案在 32 位整型范围内因此示例代码直接返回 int 没问题。但如果你在变体题里看到n很大就要立刻考虑用long做中间结果最后再按题要求取模。别等溢出才发现。s为空怎么办如果输入是空字符串循环不会执行答案就是 0。这不是边界陷阱但很多人在实现位置列表时如果pos里某些列表为空要确保第二层循环不会误操作空列表。上面代码里for (ListInteger list : pos)空列表自然跳过没问题。4. 用 DeepSeek 辅助解题提问方式决定效率4.1 我第一次提问就碰壁标题里带着 DeepSeek我也说点实际使用感受。第一次我直接把代码丢给它问“哪里错了”它回复得像模像样从“你可能没定义 countUniqueChars”一直分析到“建议用滑动窗口”。问题是它给的滑动窗口解法在这里并不适用因为countUniqueChars不是一个区间可加的简单属性滑动窗口统计不了所有子串。后来我才意识到AI 不是不行是提问太笼统。它面对“帮我看看哪里错了”这种问题时只能猜你的上下文于是给出通用但不够精准的建议。刷题时想要让 AI 真正帮上忙必须把问题拆到具体细节上。4.2 高效的追问模板与验证方法我后来总结了一套提问模板实测下来效率高很多先让它解释定义“countUniqueChars(t)在 LeetCode 828 里到底是什么意思请用ABA举例。”这一步能快速确认 AI 理解是否和你一致。如果它连“恰好出现一次”都没说基本可以断定后面回答不靠谱。再问思路方向“不要给代码先告诉我暴力枚举的复杂度瓶颈然后给一个能优化到 O(n) 的切入点。”这样能把话题强制拉回贡献法而不是让 AI 自由发挥。最后验证边界“我的实现里prev和next初始值分别用了 -1 和 n为什么这样设如果字符串为空会怎样”让它带着你过一遍边界比自己瞎猜快得多。我把这些提问整理成一段话丢给 DeepSeek它给出的解释就立刻清晰了。所以工具没问题问题在于提问人有没有把“我想解决什么”和“我现在卡在哪一步”讲清楚。AI 更像一个知识面很广的陪练你得先自己握住方向盘。4.3 把 AI 当成橡皮鸭让它挑刺还有一个我常用的习惯写完代码后不直接问“对不对”而是把核心公式描述给它听让它帮我反推。比如我会说“我假设每个位置的贡献是(i - prev[i]) * (next[i] - i)其中prev[i]是左边最近相同字符next[i]是右边最近相同字符请用s LEETCODE手算一遍看结果是不是 92。”这一步能很快暴露我对公式边界的理解是否有漏洞。有一回我故意把公式写成(i - prev[i]) * (next[i] - i 1)DeepSeek 立刻指出右边多加了 1并且用ABA的第二个 A 验证。虽然这是我自己有意写错的但至少说明它具备基础的“验算”能力。把 AI 当橡皮鸭最大的好处不是让它直接给答案而是它能逼着我把思路完整地说出来说着说着自己就发现错了。5. 这类题的变体与刷题延伸5.1 从“出现一次”改成“出现恰好 k 次”贡献法的威力不止于“恰好一次”。如果题目改成“统计所有子串中出现次数恰好为 k 的字符个数之和”思路依然成立只是状态变复杂了。对某个字符的某个出现位置它要想在子串里出现恰好 k 次那么子串左边界必须跨过这个字符的前 k-1 次出现位置但不能碰到前 k 次右边界也必须被后 k-1 次出现位置限制住。说白了原来我们只关心最近一个相同字符现在要关心“往前数第 k-1 个”和“往后数第 k-1 个”。用位置列表实现时只需要在遍历列表时用索引j取j-k1和jk左右边界就能计算出当前第j个位置在“恰好出现 k 次”的场景下能贡献多少个子串。我试着写过 k2 的版本发现只需要维护一个长度至少为 k1 的位置列表然后循环里多几次数组下标判断就行。很多人刷题只追求 AC 当前题其实把一道题改一改条件比新做十道题都更能锻炼思路。5.2 从字符贡献到价值为权重的推广贡献法的计算对象本质上是一个“位置元素”并不一定非得是字符。如果题目给每个字符一个权重w(c)要求所有子串里出现一次字符的权重和公式只需变成贡献 w(c) * (i - prev[i]) * (next[i] - i)这个推广特别实用因为它揭示了贡献法的本质一个局部性质如果能只依赖左右边界它就能被拆成每个点独立计算。字符频率、权重、甚至字符之间的距离都可能套进这个框架里。这类变体题在面试中也经常出现比如有一些题要求统计所有子数组中等于某个值的最小/最大元素贡献用的也是同样的“枚举每个元素作为最值”的思路。底层逻辑熟悉了代码无非是换一层皮。6. 实操中的常见问题与避坑清单6.1 字符串类型不一定是大写字母LeetCode 828 原题明确说明字符串只含大写英文字母所以26这个数组大小是安全的。但我在某个模拟环境里遇到过字符串包含小写字母的版本直接用char - A就会越界。如果不想纠结最稳的写法是int c s.charAt(i) - A;只在原题条件下安全。如果条件写的是“包含任意 ASCII 字符”就直接把数组长度改成 128或者用HashMapCharacter, Integer替代数组。不要一上来就写26先读清楚题目。6.2 int 溢出和取模问题这道题的答案虽然保证 int 能装下但中间乘积很可能在极端数据下先溢出。比如n 10^5某个位置贡献是(i - prev[i]) * (next[i] - i)两个乘数都可能接近 50000乘积会到 2.5e9已经超过 int 上限。别以为“最终答案不超 int”就不需要处理中间结果Java 的int乘法会在完成乘法后立即溢出。稳妥做法是把累加变量ans声明成long最后返回时再强转 int。这也是我实际提交时踩过的坑long ans 0; for (int i 0; i n; i) { ans (long)(i - prev[i]) * (next[i] - i); } return (int) ans;(long)放在乘号前能保证整个乘法按 64 位计算。别小看这一行很多时间复杂度和空间复杂度都对的人就挂在溢出上。6.3 测试边界写少了会挂在哪给你一张我当时自查用的表格照着测基本能覆盖所有坑测试用例期望结果检查点0空串循环是否正确跳过A1单个字符唯一字符贡献 1AA2两个相同字符只有长度 1 的子串贡献ABA8经典重复字符用例LEETCODE92官方示例验证整体逻辑长度 10^5 的全相同字符每个字符贡献都为 1总数 n检查是否会溢出、是否超时全相同字符的情况特别有意思比如AAAA每个位置的 A 只能在长度为 1 的子串里成为唯一所以答案就是 4。如果你把prev/next算错很容易在这个简单用例上暴露。我个人在实际操作中的体会是算法题里最容易错的从来不是高深思维而是边界条件和对定义的理解。贡献法本身不难难的是你愿不愿意先花五分钟把countUniqueChars的含义和左右边界区间画清楚。最后再分享一个小技巧做这道题时把AAA和ABA两个例子用穷举法手算一遍再对照贡献法的公式一旦能对应上整个解法就在你脑子里扎下根了。以后遇到类似“统计子串某种性质”的题不妨先试试能不能从每个字符、每个位置的角度拆开看。