C++描述 LeetCode 5677. 統計同構子字串的數目

??大家好，我叫亓官劼（qí guān jié ），在CSDN中記錄學習的點滴歷程，時光荏苒，未來可期，加油~博主目前僅在CSDN中寫博客，唯一博客更新的地址為：亓官劼的博客，同時正在嘗試在B站中做一些內容分享，B站主頁為：亓官劼的B站主頁

本文原創為亓官劼，請大家支持原創，部分平臺一直在惡意盜取博主的文章！！！
若需聯系博主，可以聯系本人微信：qiguanjie2015

給你一個字串 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 由小寫字串組成

解題思路

遍歷字串，每次記錄當前位置的值，向后遍歷，如果相同，則每次cnt+k（如果當前是連續第k個，則可以分別多1，2，3 ……k個字母的同構，所以對于第k個連續字母，cnt+k），

演算法實作

class Solution {
public:
    int countHomogenous(string s) {
        int len = s.length();
        int i = 0;
        long long int cnt = 0;
        while(i < len){
            char temp = s[i];
            cnt = (cnt + 1) % 1000000007;
            i++;
            int k = 1;
            while(s[i] == temp){
                k++;
                cnt = (cnt + k) %1000000007;
                i++;
            }
        }
        return cnt;
    }
};

亓官劼

CSDN認證博客專家 Python 全堆疊資料結構與演算法

大家好，我是亓官劼(qí guān jié)，在博客中分享資料結構與演算法、Python全堆疊開發、Java后端開發、前端、OJ題解及各類報錯資訊解決方案等經驗，一起加油，用知識改變命運，未來可期，
若有事項需聯系博主，可通過微信：qiguanjie2015 進行聯系，有慷訓回復，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259834.html

標籤：其他

上一篇：假期之不務正業—— Qt+FFmpeg+百度api進行視頻的語音識別

下一篇：docker容器開啟ssh服務