1180. Count Substrings with Only One Distinct Letter 统计只含单一字母的子串

题目地址:https://leetcode-cn.com/problems/count-substrings-with-only-one-distinct-letter/

题目描述

Given a string S, return the number of substrings that have only one distinct letter.

Example 1:

Input: S = "aaaba"
Output: 8
Explanation: The substrings with one distinct letter are "aaa", "aa", "a", "b".
"aaa" occurs 1 time.
"aa" occurs 2 times.
"a" occurs 4 times.
"b" occurs 1 time.
So the answer is 1 + 2 + 4 + 1 = 8.

Example 2:

Input: S = "aaaaaaaaaa"
Output: 55

Constraints:

1、 1<=S.length<=1000
2、 S[i]consistsofonlylowercaseEnglishletters.;

题目大意

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

解题方法

组合数

从一段长度为n的单一字母字符串中,分别选择出长度为1,2,3,...,n的子串,共有n * (n + 1) / 2个结果。

因此,遍历字符串,分别统计出单一字母字符串的长度,累加所有结果即可。

C++代码如下:

class Solution {
public:
    int countLetters(string S) {
        if (S.empty()) return 0;
        int count = 1;
        int res = 0;
        char cur = S[0];
        cout << endl;
        for (int i = 1; i <= S.size(); ++i) {
            if (i == S.size() || S[i] != cur) {
                res += count * (count + 1) / 2;
                cur = S[i];
                count = 1;
            } else {
                count ++;
            }
            
        }
        return res;
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

2022

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发