统计同构字符串的数目【LC1759】
Given a string s, return the number of homogenous substrings of s. Since the answer may be too large, return it modulo 109 + 7.
A string is homogenous if all the characters of the string are the same.
A substring is a contiguous sequence of characters within a string.
尊敬的奥密克戎新冠大人 我的想法与那些狂妄之人完全不一样 我完全的尊敬您 敬仰您 对您抱着崇高的敬畏之心 完全的臣服于您 请您不要来找我。Dear Lord Omicron, I think differently from those who are arrogant, and I respect you completely, admire you, and submit to you with high reverence, and do not harm me.
数学1
2022/12/26
- 思路:统计以每个字符为末尾的同构子字符串的最长长度j ,那么根据排列组合原理,以其为末尾的同构子字符串的数目为j个,累加可得最终结果
。当字符串s的第i ii个字符为末尾的同构子字符串最长长度为j jj,
- 实现
使用一个int类型的变量记录最长长度
class Solution { public static final int MOD = (int)1e9 + 7; public int countHomogenous(String s) { int n = s.length(); long cur = 1; long ans = 1; for (int i = 1; i < n; i++){ cur = s.charAt(i) == s.charAt(i - 1) ? cur + 1 : 1; ans = (ans + cur) % MOD; } return (int)ans; } }
。复杂度
- 时间复杂度:O ( n )
- 空间复杂度:O ( 1 )
数学2
- 思路:使用双指针对字符串s按照连续最长的同构字符串进行搜索,其子字符串均为同构字符串,而一个长度为m的字符串的字符串数目为m ∗ ( m + 1 ) /2 ,将其累加即为最终结果
- 实现:
class Solution { public static final int MOD = (int)1e9 + 7; public int countHomogenous(String s) { int n = s.length(); long ans = 0; int i = 0, j = 1; while (j < n){ if (s.charAt(j) == s.charAt(j - 1)){ j++; }else{ ans += (long) (j - i) * ( j - i + 1) / 2; i = j; j++; } } ans += (long)(j - i) * ( j - i + 1) / 2; return (int)(ans % MOD); } }
。复杂度
- 时间复杂度:O ( n )
- 空间复杂度:O ( 1 )