蚂蚁春招算法题解析：统计字符串中的好子串

1. 问题描述与理解今天我们来探讨一道来自蚂蚁集团春招的算法题题目要求统计字符串中所有满足特定条件的非空子串数量。具体来说给定一个长度为n、仅由小写字母组成的字符串s下标从1开始我们需要找出所有好子串的数量。所谓好子串是指子串中所有出现过的字符的出现次数都相等。举个例子对于字符串aabb子串aa是好的a出现2次子串aabb也是好的a和b各出现2次但子串aab不是好的a出现2次b出现1次这个问题看似简单但要在O(n²)时间复杂度内高效解决需要一些巧妙的思路。下面我将详细解析这个问题并提供Python、Java和C三种语言的实现方案。2. 解题思路分析2.1 暴力解法与优化方向最直观的暴力解法是枚举所有可能的子串然后检查每个子串是否满足条件。对于一个长度为n的字符串子串数量为O(n²)级别而检查每个子串需要O(n)时间这样总时间复杂度会达到O(n³)对于n较大的情况显然不可行。我们需要寻找一种方法能够在枚举子串的同时动态维护字符的出现次数信息从而将检查的时间复杂度降低到O(1)或O(26)因为字母表大小固定为26。2.2 滑动窗口与频次统计一个有效的策略是使用滑动窗口技术固定左端点逐步扩展右端点同时维护一个频次数组来记录当前窗口中各字符的出现次数。对于每个新加入的字符我们更新频次数组然后检查是否满足好子串的条件。检查条件的关键在于统计当前窗口中实际出现的字符频次0的字符这些字符的频次是否全部相同2.3 算法复杂度分析这种方法的时间复杂度为O(n² * 26)因为外层循环枚举左端点O(n)内层循环枚举右端点O(n)每次检查频次数组O(26)由于字母表大小固定为26我们可以认为这是一个O(n²)的算法对于n≤1000的情况完全可行。3. 代码实现详解3.1 Python实现def count_good_substrings(s): n len(s) res 0 for i in range(n): freq [0] * 26 distinct_chars set() for j in range(i, n): c ord(s[j]) - ord(a) if freq[c] 0: distinct_chars.add(c) freq[c] 1 # 检查所有出现字符的频次是否相同 first freq[next(iter(distinct_chars))] if all(freq[c] first for c in distinct_chars): res 1 return res实现要点外层循环固定左端点i内层循环扩展右端点j使用freq数组记录字符频次使用set记录当前窗口中出现的不同字符检查这些字符的频次是否全部相同3.2 Java实现public int countGoodSubstrings(String s) { int n s.length(); int res 0; for (int i 0; i n; i) { int[] freq new int[26]; SetInteger distinctChars new HashSet(); for (int j i; j n; j) { int c s.charAt(j) - a; if (freq[c] 0) { distinctChars.add(c); } freq[c]; // 检查频次是否相同 int first freq[distinctChars.iterator().next()]; boolean allSame true; for (int ch : distinctChars) { if (freq[ch] ! first) { allSame false; break; } } if (allSame) { res; } } } return res; }Java实现与Python类似但需要注意使用HashSet来记录不同字符显式地遍历set检查频次是否相同Java的字符处理需要显式转换为int3.3 C实现#include vector #include unordered_set using namespace std; int countGoodSubstrings(string s) { int n s.size(); int res 0; for (int i 0; i n; i) { vectorint freq(26, 0); unordered_setint distinct_chars; for (int j i; j n; j) { int c s[j] - a; if (freq[c] 0) { distinct_chars.insert(c); } freq[c]; // 检查频次是否相同 int first freq[*distinct_chars.begin()]; bool all_same true; for (int ch : distinct_chars) { if (freq[ch] ! first) { all_same false; break; } } if (all_same) { res; } } } return res; }C实现特点使用vector作为频次数组使用unordered_set记录不同字符通过迭代器访问set中的第一个元素4. 算法优化与变种4.1 优化频次检查当前的实现在每次扩展右端点后都需要遍历distinct_chars集合来检查频次是否相同。我们可以优化这一过程维护当前窗口中不同字符的数量维护当前窗口中所有字符的频次是否相同的标志当加入新字符或更新已有字符频次时动态更新这些状态这样可以避免每次都要遍历整个集合但实现起来会更复杂一些。4.2 处理大规模数据如果字符串长度n非常大比如1e5O(n²)的算法就不再适用。这种情况下我们需要寻找线性或O(nlogn)的解法。一个可能的方向是统计整个字符串中每个字符的总出现次数找出这些次数的最大公约数GCD基于GCD计算可能的均匀分布情况不过这种方法的正确性和实现细节还需要进一步验证。4.3 相关变种问题这类子串统计问题有很多变种比如统计所有字符都恰好出现k次的子串数量统计最多包含k个不同字符的子串数量统计不包含任何重复字符的子串数量掌握基本的滑动窗口和频次统计技术后这些变种问题都可以用类似的方法解决。5. 常见错误与调试技巧5.1 边界条件处理在实现这类算法时容易犯的边界错误包括字符串为空的情况单字符字符串所有字符都相同的情况字符串包含所有26个字母的情况提示在编写代码后务必用这些边界案例进行测试。5.2 频次数组初始化一个常见的错误是忘记在每次外层循环开始时重新初始化频次数组。如果复用同一个数组而不清零会导致统计错误。5.3 字符编码处理在不同语言中字符到数组下标的转换方式略有不同Python: ord(c) - ord(a)Java/C: c - a确保这种转换正确非常重要否则可能导致数组越界或错误的统计结果。5.4 性能优化技巧对于这类O(n²)算法即使是小的优化也能带来明显的性能提升当剩余字符不足以形成新的好子串时可以提前终止内层循环使用更高效的数据结构比如用位掩码代替set来记录出现字符在检查频次是否相同时可以记录最大和最小频次仅当两者相等时才进行完整检查6. 实际应用场景这类字符串处理算法在实际开发中有广泛的应用比如文本分析统计文档中特定模式的词频生物信息学DNA序列的模式匹配数据压缩寻找重复出现的子串模式拼写检查查找接近特定模式的单词理解这类基础算法不仅能帮助通过技术面试也能为实际工作中的文本处理问题提供解决思路。7. 个人实现心得在实际编写这类算法时我发现以下几点特别重要先写出暴力解法再考虑优化。虽然暴力解法可能效率不高但它能帮助我们全面理解问题。使用具体的例子来验证思路。比如用aabb、abc这样的简单字符串手动模拟算法执行过程。频次统计类问题数组通常比哈希表更高效特别是当键的范围已知且不大时如26个字母。在面试中即使不能立即想到最优解也应该清晰地表达自己的思考过程面试官往往更看重解题思路而非完美的代码。这道题虽然不算很难但它很好地考察了候选人对字符串处理、滑动窗口和频次统计等基础算法的掌握程度。在蚂蚁集团这类公司的面试中类似的题目经常出现因为它们能有效区分不同水平的候选人。