在这篇文章中，我们将深入探讨一个既经典又非常实用的字符串算法问题：计算一个字符串中由相同字符组成的子串数量。这不仅仅是一道算法竞赛题，更是考察我们对字符串遍历、逻辑思维以及时间复杂度优化的绝佳练习。我们将一起分析问题的本质，探索最优解法，并深入探讨代码实现的每一个细节，确保你不仅能写出代码，还能理解背后的设计思想。
问题背景与核心目标
首先，让我们明确一下具体的目标。给定一个字符串，我们需要找出所有子串中，只包含一种字符的子串总数。请注意，这里说的“子串”指的是原字符串中字符连续的序列，这与“子序列”是不同的。
为了让你更直观地理解，让我们看一个简单的例子。
示例分析：
假设输入字符串是 "abc"。
我们可以列出所有的子串：
- 长度为1的："a", "b", "c" （共3个）
- 长度为2的："ab", "bc" （共2个）
- 长度为3的："abc" （共1个）
题目要求的是由相同字符组成的子串。在上面的列表中，只有长度为1的 "a", "b", "c" 符合条件。"ab" 包含了不同的字符，"bc" 也一样，"abc" 也是混合的。所以答案是 3。
再来看一个稍微复杂点的例子：
假设输入字符串是 "abbba"。
符合条件的子串有：
- "a" (索引0)
- "a" (索引4)
- "b" (索引1), "b" (索引2), "b" (索引3)
- 连续的相同字符组成的更长子串：
– 中间的三个 ‘b‘ 组成了 "bb" (1-2), "bb" (2-3) 以及 "bbb" (1-3)。
如果你把上面的所有情况加起来，你会发现这其实是一个数学组合问题。这正是我们接下来要讨论的核心解法。
初步探索：暴力解法为何不可行
在寻找最优解之前，我们通常会先想到暴力解法，也就是生成所有的子串，然后逐一检查它们是否只由一种字符组成。
对于长度为 $n$ 的字符串，子串的总数是 $O(n^2)$ 级别的（因为总共有 $n(n+1)/2$ 个子串）。如果对于每一个子串，我们再去遍历检查字符是否相同，那么总的时间复杂度就会上升到 $O(n^3)$。当字符串长度稍微增加（比如超过1000），这种方法的计算量就会变得非常巨大，导致程序运行超时。
显然，我们需要一种更聪明的方法，将时间复杂度降低到 $O(n)$。
深入剖析：最优解法思路
让我们换个角度思考。与其检查每一个子串，不如统计连续相同字符的片段。
想象一下，你正在扫描这个字符串。当你遇到一段连续的相同字符时，比如 "aaaa"，这段字符内部会包含多少个符合条件的子串呢？
- 长度为1的子串："a", "a", "a", "a" （4个）
- 长度为2的子串："aa", "aa", "aa" （3个）
- 长度为3的子串："aaa", "aaa" （2个）
- 长度为4的子串："aaaa" （1个）
总数量 = $4 + 3 + 2 + 1 = 10$。
这正好是一个等差数列求和公式！对于一段长度为 $k$ 的连续相同字符，它包含的符合条件的子串数量为：
$$ \text{Count} = \frac{k \times (k + 1)}{2} $$
我们的策略变得非常清晰：
- 遍历字符串，寻找当前连续相同字符的“块”。
- 记录这个“块”的长度 $k$。
- 一旦遇到不同的字符（或者到达字符串末尾），利用上面的公式计算当前“块”的贡献，并累加到总结果中。
- 重置计数器，继续处理后续的字符。
这种方法只需要遍历字符串一次，因此时间复杂度是 $O(n)$，空间复杂度是 $O(1)$（只用了几个变量），这是极其高效的。
代码实现与详细注释
接下来，让我们看看如何将这个思路转化为具体的代码。为了满足不同开发环境的需求，我将为你提供 C++、Java、Python3 和 C# 四种语言的实现。
#### 1. C++ 实现
C++ 以其高性能著称，非常适合处理这类底层的字符串操作。
// C++ 实现：计算由相同字符组成的子串数量
#include
#include
#include
using namespace std;
// 函数：计算并返回结果
long long countSubstrings(string s) {
// 处理边界情况：空字符串
if (s.empty()) return 0;
int n = s.length();
long long result = 0; // 使用 long long 防止大数溢出
int count = 1; // 计数器，初始为1，因为非空字符串至少有一个字符
// 从第二个字符开始遍历，与它的前一个字符进行比较
for (int i = 1; i < n; i++) {
// 如果当前字符与前一个字符相同
if (s[i] == s[i - 1]) {
count++;
}
// 如果遇到了不同的字符，说明上一个连续的“块”结束了
else {
// 累加当前块的子串数量：count * (count + 1) / 2
result += count * (count + 1) / 2;
// 重置计数器，开始计算新的字符块
count = 1;
}
}
// 别忘了处理最后一个字符块！
// 因为循环遇到不同的字符才结算，所以最后一段需要手动加上
result += count * (count + 1) / 2;
return result;
}
// Driver Code - 测试我们的逻辑
int main() {
string s1 = "abc";
cout << "Input: " << s1 < Output: " << countSubstrings(s1) << endl;
string s2 = "abbba";
cout << "Input: " << s2 < Output: " << countSubstrings(s2) << endl;
string s3 = "bbbcbb";
cout << "Input: " << s3 < Output: " << countSubstrings(s3) << endl;
return 0;
}
关键点解析：
- 注意我们使用 INLINECODE96909ff9 类型来存储 INLINECODEa048fb89。虽然字符串长度可能不大，但如果字符串非常长且全是同一个字符（例如一万个 ‘a‘），计算出的子串数量会非常巨大（约5000万），普通的
int可能会溢出。 - 循环后的处理：这是新手最容易犯错的地方。循环内部只在字符发生变化时结算，因此字符串末尾的最后一段连续字符不会被处理，必须在循环结束后手动加一次。
#### 2. Java 实现
在 Java 中，字符串处理通常比较直观，charAt(i) 是我们常用的方法。
// Java 实现：计算由相同字符组成的子串数量
public class SameCharacterSubstrings {
public static long countSubstrings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
long result = 0;
int count = 1;
int n = s.length();
// 从索引 1 开始遍历
for (int i = 1; i < n; i++) {
// 比较当前字符和前一个字符
if (s.charAt(i) == s.charAt(i - 1)) {
count++;
} else {
// 字符不同，结算前一段
result += count * (count + 1) / 2;
count = 1;
}
}
// 处理最后一段连续字符
result += count * (count + 1) / 2;
return result;
}
public static void main(String[] args) {
String input = "bbbcbb";
System.out.println("输入: " + input);
System.out.println("输出: " + countSubstrings(input));
// 更多测试用例
System.out.println("测试 'aaa': " + countSubstrings("aaa")); // 期望: 6
System.out.println("测试 'ab': " + countSubstrings("ab")); // 期望: 2
}
}
#### 3. Python3 实现
Python 的代码通常最为简洁，我们可以利用它强大的列表切片或者简单的遍历来解决问题。这里为了展示算法通用性，我们使用常规遍历法。
# Python3 实现：计算由相同字符组成的子串数量
def count_substrings(s):
if not s:
return 0
n = len(s)
result = 0
count = 1
# 遍历字符串，从第二个字符开始
for i in range(1, n):
# 比较当前字符与前一个字符
if s[i] == s[i-1]:
count += 1
else:
# 字符不同，结算当前连续块
result += count * (count + 1) // 2
count = 1
# 别忘了加上最后一部分的数量
result += count * (count + 1) // 2
return result
# 测试代码
if __name__ == "__main__":
test_str = "bbbcbb"
print(f"输入字符串: {test_str}")
print(f"符合条件的子串数量: {count_substrings(test_str)}")
# 验证公式："bbbcbb" 可以看作 bbb(6个) + c(1个) + bb(3个) = 10
# 3个b: 3*4/2 = 6
# 1个c: 1*2/2 = 1
# 2个b: 2*3/2 = 3
# Total = 10
#### 4. C# 实现
对于 C# 开发者，代码结构与 Java 非常相似。
using System;
class Program
{
// 函数：计算数量
static long CountSubstrings(string s)
{
if (string.IsNullOrEmpty(s)) return 0;
long result = 0;
int count = 1;
int n = s.Length;
for (int i = 1; i < n; i++)
{
if (s[i] == s[i - 1])
{
count++;
}
else
{
result += count * (count + 1) / 2;
count = 1;
}
}
// 处理最后一组连续字符
result += count * (count + 1) / 2;
return result;
}
static void Main()
{
string input = "bbbcbb";
Console.WriteLine($"字符串: {input}");
Console.WriteLine($"结果: {CountSubstrings(input)}");
}
}
复杂度分析与最佳实践
作为一名追求卓越的开发者，我们不能仅仅满足于代码能跑通，还需要关注性能和健壮性。
#### 时间复杂度
正如我们前面分析的，算法只需要对数组进行一次完整的遍历。随着字符串长度 $n$ 的增加，操作次数线性增长。因此，时间复杂度为 $O(n)$。
#### 空间复杂度
我们没有使用额外的数据结构（如哈希表或数组）来存储中间状态，只用了几个简单的变量（INLINECODE7a611b95, INLINECODE8b9c30cc, i）。因此，空间复杂度为 $O(1)$，这是最优的空间利用率。
#### 潜在的陷阱与解决方案
在编写这段代码时，有几个细节需要你特别注意：
- 整数溢出：这是一个经典的 Bug 来源。计算公式 INLINECODEb303dea5 中，如果 INLINECODE4127f849 很大（例如接近 $2^{31}$），那么乘法运算的结果可能会超过 32 位整数的上限。在 C++ 或 Java 中，务必使用 INLINECODE2b9424d2 或 INLINECODE27a04331 类型来接收结果。
- 空字符串处理：在函数开头，一定要检查输入字符串是否为空或 INLINECODEbc5e7551。如果不检查，直接访问 INLINECODE4769c3ee 或调用
length()可能会导致程序崩溃（特别是 C++ 访问空字符串内存时）。 - 单字符字符串：如果输入是 "a"，循环可能不会执行（因为 INLINECODE254e8c26 从 1 开始），或者 INLINECODEd0a2a522 分支不会触发。循环结束后的
result += ...这一步至关重要，它保证了单字符的情况也能被正确计算（结果为 1）。
进阶思考：如果字符非连续呢？
为了加深你的理解，让我们思考一个变种问题：如果我们要计算由相同字符组成的子序列数量，该如何处理？
这会变成一个更复杂的动态规划问题。例如 "abca"，子序列 "aa" 就算数，即使它们不连续。这时，我们需要统计每种字符出现的总次数 $m$，然后对每种字符计算 $C(m, 1) + C(m, 2) + \dots + C(m, m)$，这其实是 $2^m – 1$。当然，这属于另一个话题了，但它能很好地帮助你理解“子串”与“子序列”的本质区别。
总结
在这篇文章中，我们通过一道经典的字符串题目，学习了如何将数学思维应用到编程算法中。通过将大问题拆解为寻找“连续相同字符块”的小问题，我们成功地将一个看似需要 $O(n^3)$ 复杂度的任务优化到了 $O(n)$。
关键在于：
- 识别问题的数学规律（等差数列求和）。
- 采用一次遍历的策略，减少不必要的重复计算。
- 注意代码的边界条件（循环后的最后一次累加）和溢出风险。
希望这种从“暴力”到“优化”的思考过程能对你有所启发。下次当你面对字符串处理问题时，不妨先停下来观察一下数据分布的规律，也许一个简单的数学公式就能帮你省去大量的计算资源。快去你的代码编辑器中试一试吧！