跳转至

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

来源第 8 场双周赛 Q1难度简单分数1315

题目描述

给你一个字符串 s，返回 只含 单一字母 的子串个数 。

示例 1：

输入： s = "aaaba"
输出： 8
解释： 只含单一字母的子串分别是 "aaa"， "aa"， "a"， "b"。
"aaa" 出现 1 次。
"aa" 出现 2 次。
"a" 出现 4 次。
"b" 出现 1 次。
所以答案是 1 + 2 + 4 + 1 = 8。

示例 2:

输入： s = "aaaaaaaaaa"
输出： 55

 

提示：

  • 1 <= s.length <= 1000
  • s[i] 仅由小写英文字母组成

解法

方法一：双指针

思考

仅含一种字母的子串必落在一段连续相同字符内。长为 \(L\) 的段贡献 \(L(L+1)/2\) 个子串。双指针切出每段长度，按三角数累加，不必枚举全部 \(O(n^2)\) 子串。

我们可以使用双指针，用指针 \(i\) 指向当前子串的起始位置，指针 \(j\) 向右移动到第一个与 \(s[i]\) 不同的位置，那么 \([i,..j-1]\) 就是以 \(s[i]\) 为唯一字母的子串，长度为 \(j-i\)，那么以 \(s[i]\) 为唯一字母的子串的个数就是 \(\frac{(j-i+1)(j-i)}{2}\)，累加到答案中。然后令 \(i=j\)，继续遍历，直到 \(i\) 超出字符串 \(s\) 的范围。

时间复杂度 \(O(n)\)，其中 \(n\) 是字符串 \(s\) 的长度。空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def countLetters(self, s: str) -> int:
        n = len(s)
        i = ans = 0
        while i < n:
            j = i
            while j < n and s[j] == s[i]:
                j += 1
            ans += (1 + j - i) * (j - i) // 2
            i = j
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int countLetters(String s) {
        int ans = 0;
        for (int i = 0, n = s.length(); i < n;) {
            int j = i;
            while (j < n && s.charAt(j) == s.charAt(i)) {
                ++j;
            }
            ans += (1 + j - i) * (j - i) / 2;
            i = j;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int countLetters(string s) {
        int ans = 0;
        for (int i = 0, n = s.size(); i < n;) {
            int j = i;
            while (j < n && s[j] == s[i]) {
                ++j;
            }
            ans += (1 + j - i) * (j - i) / 2;
            i = j;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func countLetters(s string) int {
    ans := 0
    for i, n := 0, len(s); i < n; {
        j := i
        for j < n && s[j] == s[i] {
            j++
        }
        ans += (1 + j - i) * (j - i) / 2
        i = j
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function countLetters(s: string): number {
    let ans = 0;
    const n = s.length;
    for (let i = 0; i < n;) {
        let j = i;
        let cnt = 0;
        while (j < n && s[j] === s[i]) {
            ++j;
            ans += ++cnt;
        }
        i = j;
    }
    return ans;
}

方法二

思考

方法一用闭式一次加上整段贡献。方法二在扩展段时用计数器 \(1,2,\ldots,L\) 逐个累加，和仍为三角数，便于理解「以当前字符结尾的单字母子串」个数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def countLetters(self, s: str) -> int:
        ans = 0
        i, n = 0, len(s)
        while i < n:
            j = i
            cnt = 0
            while j < n and s[j] == s[i]:
                j += 1
                cnt += 1
                ans += cnt
            i = j
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int countLetters(String s) {
        int ans = 0;
        int i = 0, n = s.length();
        while (i < n) {
            int j = i;
            int cnt = 0;
            while (j < n && s.charAt(j) == s.charAt(i)) {
                ++j;
                ans += ++cnt;
            }
            i = j;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int countLetters(string s) {
        int ans = 0;
        int i = 0, n = s.size();
        while (i < n) {
            int j = i;
            int cnt = 0;
            while (j < n && s[j] == s[i]) {
                ++j;
                ans += ++cnt;
            }
            i = j;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func countLetters(s string) (ans int) {
    i, n := 0, len(s)
    for i < n {
        j := i
        cnt := 0
        for j < n && s[j] == s[i] {
            j++
            cnt++
            ans += cnt
        }
        i = j
    }
    return
}

评论