【每日一题Day68】LC1759 统计同构字符串的数目 | 数学

简介: 思路:统计以每个字符为末尾的同构子字符串的最长长度j ,那么根据排列组合原理,以其为末尾的同构子字符串的数目为j个,累加可得最终结果

统计同构字符串的数目【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 )
目录
相关文章
|
7月前
【每日一题Day118】LC1124表现良好的最长时间段 | 前缀和+单调栈/哈希表
【每日一题Day118】LC1124表现良好的最长时间段 | 前缀和+单调栈/哈希表
57 0
|
7月前
【每日一题Day159】LC1638统计只差一个字符的子串数目 | 枚举
【每日一题Day159】LC1638统计只差一个字符的子串数目 | 枚举
41 0
|
7月前
【每日一题Day155】LC1630等差子数组 | 枚举+排序
【每日一题Day155】LC1630等差子数组 | 枚举+排序
46 0
|
7月前
|
算法 测试技术 C#
【多数组合 数学 字符串】2514. 统计同位异构字符串数目
【多数组合 数学 字符串】2514. 统计同位异构字符串数目
|
7月前
【每日一题Day371】LC2586统计范围内的元音字符串数 | 模拟
【每日一题Day371】LC2586统计范围内的元音字符串数 | 模拟
57 1
|
7月前
【每日一题Day241】LC1254统计封闭岛屿的数目 | dfs
【每日一题Day241】LC1254统计封闭岛屿的数目 | dfs
50 1
|
7月前
【每日一题Day277】LC2569更新数组后处理求和查询 | 线段树
【每日一题Day277】LC2569更新数组后处理求和查询 | 线段树
38 0
|
7月前
【每日一题Day236】LC2475数组中不等三元组的数目
【每日一题Day236】LC2475数组中不等三元组的数目
37 0
|
7月前
|
算法
算法编程(二十九):统计一致字符串的数目
算法编程(二十九):统计一致字符串的数目
85 0
|
算法
代码随想录算法训练营第二十六天 | LeetCode 39. 组合总和、40. 组合总和 II、131. 分割回文串
代码随想录算法训练营第二十六天 | LeetCode 39. 组合总和、40. 组合总和 II、131. 分割回文串
50 0