LEETCODE 1180. Count Substrings with Only One Distinct Letter 解题思路分析

题目大意：

统计只含单一字母的子串

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

示例1：

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

示例 2:

输入: S = "aaaaaaaaaa" 
输出: 55 

提示：

1. 1 <= S.length <= 1000
2. S[i] 仅由小写英文字母组成。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1180

解题思路分析：

目的是统计只含单一字母的子串，也就是说子字符串中只能含有一种字符，那么我们可以将字符串中连续相同的部分分开，比如aaaba可以分成aaa，b，a三部分。接下来就是如何求某一长度的字符串能产生几种子字符串的问题。这其实是等差数列求和问题。比如字符串aaa。长度为3的个数只有1个，长度为2的有2个，长度为1的有3个。结果就是1+2+3。 同理例如aaaaaaaaaa（10个a），结果应该是1+2+3+…+9+10=55。这样我们求出所有分割后的子字符串的等差数列和，再相加即是返回结果。

实现代码：

public int countLetters(String S) {
    int sameLength=1; // 当前连续相同字符的个数
    int res=1; // 返回结果
    // 从下标1（第2位）开始循环
    for(int i=1;i<S.length();i++){
        // 如果当前字符与前一位不同
        if(S.charAt(i)!=S.charAt(i-1)){
            // sameLength还原为1（长度为当前字符）
            sameLength=1;
        }else{
            // 如果与前字符相同，sameLength加一。
            // 这一步相当于制作等差数列
            sameLength++;
        }
        // 将sameLength加入返回结果
        res+=sameLength;
    }
    return res;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Count Substrings with Only One Distinct Letter.

Memory Usage: 34.2 MB, less than 100.00% of Java online submissions for Count Substrings with Only One Distinct Letter.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1180-count-substrings-with-only-one-distinct-letter-解题思路分析/