1.題目描述
1759. 統(tǒng)計(jì)同構(gòu)子字符串的數(shù)目
難度中等43
給你一個(gè)字符串 s 庵佣，返回 s 中 同構(gòu)子字符串 的數(shù)目义钉。由于答案可能很大师抄，只需返回對(duì) 109 + 7 取余 后的結(jié)果。
同構(gòu)字符串 的定義為：如果一個(gè)字符串中的所有字符都相同，那么該字符串就是同構(gòu)字符串。
子字符串 是字符串中的一個(gè)連續(xù)字符序列。
示例 1：
輸入：s = "abbcccaa"
輸出：13
解釋?zhuān)和瑯?gòu)子字符串如下所列：
"a" 出現(xiàn) 3 次。
"aa" 出現(xiàn) 1 次抹蚀。
"b" 出現(xiàn) 2 次。
"bb" 出現(xiàn) 1 次企垦。
"c" 出現(xiàn) 3 次环壤。
"cc" 出現(xiàn) 2 次。
"ccc" 出現(xiàn) 1 次钞诡。
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13
示例 2：
輸入：s = "xy"
輸出：2
解釋?zhuān)和瑯?gòu)子字符串是 "x" 和 "y" 郑现。
示例 3：
輸入：s = "zzzzz"
輸出：15
2.解題思路與代碼
2.1 解題思路
典型的滑動(dòng)窗口題目，我們使用 left 和 right 兩個(gè)指針來(lái)表示滑動(dòng)窗口的左右邊界荧降，首先記錄初始位置的字符 ch接箫，然后開(kāi)始移動(dòng)右邊界 right，并記錄 right 位置上的字符朵诫。此時(shí)比較 right 上的字符與前面記錄的字符是否相同辛友，如果相同統(tǒng)計(jì)當(dāng)前窗口字符數(shù)并累加到結(jié)果上即 ans+=right-left+1。如果不相同說(shuō)明前面一個(gè)相同字符子串已經(jīng)結(jié)束剪返，縮小窗口废累，讓 left 移動(dòng)到 right 上重新開(kāi)始計(jì)算，并將 ch 記錄當(dāng)前 right 位置上的字符脱盲，由于單個(gè)字符也算相同字符子串邑滨，因此也要累加計(jì)算 ans+=right-left+1。
以字符串 “abbcccaa” 為例钱反，初始化才開(kāi)始的時(shí)候讓 left 和 right 指向 0 位置掖看，并且此時(shí) ch 記錄 'a'。
開(kāi)始移動(dòng) right 面哥，當(dāng) right 移動(dòng)到 b 時(shí)乙各，此時(shí) right 字符與 ch 記錄不同，需要將 left 移動(dòng)到 right 位置并重新記錄 ch 為當(dāng)前 right 字符 'b'
繼續(xù)移動(dòng) right 直到 right 指向字符 c幢竹，此時(shí)將 left 移動(dòng)到 right 并在此記錄 ch 為字符 'c'。重復(fù)這一系列操作直到字符串遍歷完成恩静。最后返回 ans 即可焕毫。
2.2 代碼
class Solution {
public int countHomogenous(String s) {
long ans = 0;
int l = 0, r = 0;
char ch = s.charAt(r);
while (r < s.length()) {
if (ch!=s.charAt(r)){
l = r;
ch = s.charAt(r);
}
ans += r - l + 1;
r++;
}
return (int) (ans % (Math.pow(10, 9) + 7));
}
}
2.3 測(cè)試結(jié)果
通過(guò)測(cè)試
3.總結(jié)
- 使用字符 ch 記錄字符蹲坷，并用滑動(dòng)窗口統(tǒng)計(jì)子串個(gè)數(shù)
- 如果遇到不同字符移動(dòng) left 到 right 位置并重新記錄 ch 為當(dāng)前字符
