---

1180. 统计只含单一字母的子串

• 标签：数学、字符串
• 难度：简单

题目链接

• 1180. 统计只含单一字母的子串 - 力扣

题目大意

描述：给定一个字符串 $s$。

要求：统计所有字符都相同的子串有多少个。

说明：

• $1 \le s.length \le 10^3$。
• $s[i]$ 仅由小写英文字母组成。

示例：

• 示例 1：

输入：s = "aaaba"
输出：8
解释：
所有字符都相同的子串有：
"aaa"（位置 [0,1,2]）—— 1 个
"aa"（位置 [0,1]）   —— 1 个
"aa"（位置 [1,2]）   —— 1 个
"a"（位置 [0]）      —— 1 个
"a"（位置 [1]）      —— 1 个
"a"（位置 [2]）      —— 1 个
"a"（位置 [3]）      —— 1 个
"b"（位置 [4]）      —— 1 个
总共 8 个。

解题思路

思路 1：双指针找连续段

这道题的关键在于找到字符串中连续相同字母组成的「段」。比如 "aaaba" 中，"aaa" 是一个段，"b" 是一个段，"a" 是一个段。

如果一个连续段长度为 $len$，它能产生多少个「所有字符都相同」的子串？

举个例子，"aaa"（长度 3）能产生：

• 长度为 1 的子串："a"、"a"、"a" → 3 个
• 长度为 2 的子串："aa"、"aa" → 2 个
• 长度为 3 的子串："aaa" → 1 个
• 总共：$3 + 2 + 1 = 6$ 个

这其实是一个数学公式：长度为 $len$ 的连续段，产生的子串数量 = $len \times (len + 1) \div 2$。

为什么？因为可以从 $len$ 个位置中任选连续的一段，选择方式就是 $\frac{len \times (len + 1)}{2}$。

步骤拆解：

1. 用两个指针（或者说一个指针 $i$ 和一个移动的 $j$）遍历字符串。
2. $i$ 指向当前段的开头，让 $j$ 从 $i$ 开始往后走，直到遇到不同的字母。
3. 此时 $j - i$ 就是当前段的长度。
4. 用公式 $length \times (length + 1) // 2$ 算出能产生的子串数，加到结果里。
5. 把 $i$ 移到 $j$ 的位置，开始处理下一段。
6. 重复直到字符串末尾。

为什么用双指针？ 因为可以一次性跳过一整段相同字符，不用一个字符一个字符地慢慢数。

思路 1：代码

class Solution:
    def countLetters(self, s: str) -> int:
        if not s:
            return 0
        
        result = 0
        i = 0           # 当前段的起始位置
        n = len(s)
        
        while i < n:
            j = i
            # 让 j 往前走，直到遇到不同的字母或走到末尾
            while j < n and s[j] == s[i]:
                j += 1
            
            # 计算当前段的长度
            length = j - i
            
            # 长度为 length 的连续段，能产生 length * (length + 1) / 2 个子串
            result += length * (length + 1) // 2
            
            # 从下一段开始继续
            i = j
        
        return result

思路 1：复杂度分析

• 时间复杂度：$O(n)$。用人话说就是：每个字符只被访问一次，$n$ 是字符串长度。字符串多长我们就跑多快。
• 空间复杂度：$O(1)$。只用了几个固定变量。