1. 问题解析理解题目核心要求LeetCode 1358题要求我们统计给定字符串中所有包含至少一个a、b、c三种字符的子字符串数量。这个问题看似简单但要在O(n)时间复杂度内解决需要巧妙的算法设计。举个例子对于字符串abcabc有效的子串包括abc、abca、abcab、abcabc、bca、bcab、bcabc、cab、cabc、abc(第二个)等总共有10个符合条件的子串这个问题的难点在于如何高效地统计所有满足条件的子串而不用暴力枚举所有可能的子串组合。我们需要找到一个能够利用之前计算结果的方法避免重复计算。2. 动态规划解法思路拆解2.1 基本DP思路动态规划的核心思想是利用已经计算过的结果来推导新的结果。对于这个问题我们可以定义dp[i]表示以s[0]开头s[i]结尾的所有子串中满足条件的数量这样当我们计算dp[i]时可以利用dp[i-1]的结果只需要考虑新增字符s[i]带来的影响。具体来说我们需要找到所有以s[i]结尾且包含a、b、c三种字符的子串。2.2 滑动窗口优化为了高效地判断当前窗口是否包含所有三种字符我们使用滑动窗口技术配合哈希表记录字符频次维护一个窗口[l, i]初始l0当窗口内包含所有三种字符时尝试缩小左边界l记录第一个使得窗口恰好包含所有三种字符的位置j则所有以s[i]结尾的有效子串数量为j1因为s[0..j]到s[i]都满足这种方法的优势在于每个字符最多被访问两次进入和离开窗口因此时间复杂度是O(n)。3. 代码实现详解3.1 主算法实现class Solution { public: int numberOfSubstrings(string s) { int n s.size(), pre 0, l 0, all -1; vectorint dp(n, 0), arr; vectorint te(3, 0); // 将字符转换为0(a),1(b),2(c)方便数组索引 for(char c : s) arr.push_back(c - a); // 初始化前两个字符的计数 for(int i 0; i 2; i) te[arr[i]]; for(int i 2; i n; i) { te[arr[i]]; // 新增当前字符计数 // 如果还没有收集全三种字符跳过 if(all 0 (te[0]0 || te[1]0 || te[2]0)) continue; all 1; // 标记已经收集全过三种字符 // 处理连续相同字符的情况避免重复计算 if(i 0 s[i]s[i-1]) { dp[i] pre dp[i-1]; continue; } // 滑动窗口左边界调整 for(int j l; j i; j) { if(te[arr[j]] 1) { // 这是该字符的唯一一个 pre j 1; // 记录有效左边界 l j; // 更新滑动窗口左边界 dp[i] pre dp[i-1]; // 计算当前dp值 break; } te[arr[j]]--; // 可以安全地移除这个字符 } } return dp[n-1]; } };3.2 关键代码段解析字符转换将字符a,b,c转换为0,1,2方便数组索引滑动窗口维护te数组记录当前窗口内各字符的数量当窗口包含所有三种字符时尝试右移左边界当某个字符数量减到1时停止此时窗口是满足条件的最小窗口DP状态转移如果当前字符与前一个相同直接利用之前的结果否则计算新的有效左边界并更新dp值3.3 时间复杂度分析外层循环遍历整个字符串O(n)内层while循环每个字符最多被处理两次进入和离开窗口总体时间复杂度O(n)空间复杂度O(n)dp数组4. 优化思路与替代方案4.1 滑动窗口的另一种实现int numberOfSubstrings(string s) { int count[3] {0, 0, 0}; int res 0, left 0; for (int right 0; right s.size(); right) { count[s[right] - a]; while (count[0] count[1] count[2]) { res s.size() - right; count[s[left] - a]--; } } return res; }这种实现更加简洁维护一个滑动窗口[left, right]当窗口包含所有三种字符时所有以right结尾的子串都满足条件共n-right个然后尝试右移left缩小窗口不需要额外的dp数组空间复杂度降为O(1)4.2 暴力解法的局限性原始问题描述中给出的暴力解法虽然直观但时间复杂度为O(n^2)无法通过LeetCode的大数据测试class Solution { public: int numberOfSubstrings(string s) { int n s.size(); vectorint dp(n, 0); for(int i 0; i n; i) { unordered_setchar te {s[i]}; for(int j i - 1; j 0; j--) { te.insert(s[j]); if(te.size() 3) { dp[i] j 1 dp[i-1]; break; } } } return dp[n-1]; } };这种解法的问题在于对于每个i都要向前扫描直到找到三个不同字符最坏情况下时间复杂度为O(n^2)使用unordered_set带来了额外的开销5. 常见问题与调试技巧5.1 边界条件处理字符串长度小于3直接返回0因为不可能包含三种字符字符串只有一种或两种字符同样返回0连续相同字符需要特殊处理避免重复计算5.2 调试技巧打印中间状态在关键步骤打印dp数组和窗口状态cout i i dp dp[i] l l te[ te[0] , te[1] , te[2] ] endl;小规模测试用例先用简单例子验证如abc、aabbcc等性能分析对于长字符串检查算法是否真的线性时间5.3 常见错误滑动窗口边界处理不当可能导致漏算或多算确保在缩小窗口时正确处理字符计数注意更新窗口左边界的位置DP状态转移错误连续相同字符时的特殊处理dp[i]的计算要准确包含所有可能性初始化问题dp数组和计数数组的初始值要正确前两个字符需要单独初始化6. 算法扩展与应用6.1 类似问题最少包含K种字符的子串数将条件从3种扩展到K种最长包含K种字符的子串求满足条件的子串的最大长度恰好包含K种字符的子串数统计恰好包含K种字符的子串数量6.2 实际应用场景DNA序列分析统计包含特定碱基组合的子序列文本挖掘查找包含特定关键词组合的文本片段数据流分析实时监控数据流中特定模式的出现6.3 性能优化进阶对于更严格的性能要求可以考虑位运算优化用位掩码代替计数数组并行计算对于超长字符串可以分段处理预处理技术预先记录每个字符的位置加速窗口移动在实际编码面试中建议先提出暴力解法然后逐步优化到滑动窗口方案并讨论时间空间复杂度。同时要注意代码的整洁性和边界条件的处理。
