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]，初始l=0
- 当窗口内包含所有三种字符时，尝试缩小左边界l
- 记录第一个使得窗口恰好包含所有三种字符的位置j
- 则所有以s[i]结尾的有效子串数量为j+1（因为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; vector<int> dp(n, 0), arr; vector<int> 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(); vector<int> dp(n, 0); for(int i = 0; i < n; i++) { unordered_set<char> 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 性能优化进阶
对于更严格的性能要求，可以考虑：
- 位运算优化：用位掩码代替计数数组
- 并行计算：对于超长字符串，可以分段处理
- 预处理技术：预先记录每个字符的位置，加速窗口移动
在实际编码面试中，建议先提出暴力解法，然后逐步优化到滑动窗口方案，并讨论时间空间复杂度。同时要注意代码的整洁性和边界条件的处理。