首页 🍒LeetCode,🐶算法

题目

给你一个字符串 s ,返回 s 中 同构子字符串 的数目。由于答案可能很大,只需返回对 109 + 7 取余 后的结果。

同构字符串 的定义为:如果一个字符串中的所有字符都相同,那么该字符串就是同构字符串。

子字符串 是字符串中的一个连续字符序列。

 

示例 1:

输入:s = "abbcccaa"
输出:13
解释:同构子字符串如下所列:
"a" 出现 3 次。
"aa" 出现 1 次。
"b" 出现 2 次。
"bb" 出现 1 次。
"c" 出现 3 次。
"cc" 出现 2 次。
"ccc" 出现 1 次。
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13
示例 2:

输入:s = "xy"
输出:2
解释:同构子字符串是 "x" 和 "y" 。
示例 3:

输入:s = "zzzzz"
输出:15
 

提示:

1 <= s.length <= 105
s 由小写字符串组成

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-number-of-homogenous-substrings
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

一个同构字符串比如"zzzzz"可以提供5个z,4个zz,3个zzz,2个zzzz,1个zzzzz。
所以一个同构字符串"zzzzz"可以提供13个同构子字符串,就是5 + 4 + 3 + 2 + 1.
知道这个了的话就可以把每个子字符串可以产生的同构字符串求出。
最后注意题目要求的结果取余,还有long long

class Solution {
public:
    long long maxnum(string str) {
        long long max = 0;
        for (long long i = 1; i <= str.size(); i++) {
            max += i;
        }    
        return max;
    }
    
    int countHomogenous(string s) {
        if (s.size() == 0) return 0;
        long long num = 0;
        string str;
        str += s[0];
        for (int i = 1; i < s.size(); i++) {
            if (s[i - 1] != s[i]) {
                num += maxnum(str);
                str = "";
            }
            str += s[i];
        }
        num += maxnum(str);
        return num % (long(pow(10, 9)) + 7);
    }
};



文章评论