力扣(LeetCode)1759. 统计同构子字符串的数目(C++)_学习

力扣(LeetCode)1759. 统计同构子字符串的数目(C++)

创始人

2024-05-01 06:01:02

题目描述

双指针数学

根据同构字符串的定义，还有示例，发现同构子字符串的数量，只和字母相同的区间有关。如abbcccaa，有 444 个影响答案的区间，直观切分为a bb ccc aa，用空格划分区间。遍历的任务就是维护这些区间，通过区间长度，维护答案。本题的滑动窗口①_①①维护字母相同的连续字符串。

区间与答案的关系 : 考虑如何划分子字符串，可以按照长度，划分为单字母，双字母 …\dots… 整个区间。由于连续的要求，对应的子字符串数量 : 1->len , 2->len-1 , 3->len-2 ... len-1->2 , len->1，箭头左侧是子字符串长度，右侧是子字符串数量。

名词解释

①滑动窗口 : 遍历字符串，维护连续区间的算法，称为滑动窗口，是双指针的经典应用。

核心代码

class Solution {
public:int countHomogenous(string s) {int l = 0,r = 0;int ans = 0;const int mod = 1e9+7;while(rwhile(s[r]==s[l]) r++;int len = r-l;ans =(ans + (long long)(len+1)*len/2)%mod;l = r;}return (ans+(long long)(r-l+1)*(r-l)/2)%mod;}
};

时间复杂度 : O(n)O(n)O(n) ， nnn 是字符串长度，一次遍历维护滑动窗口的时间复杂度 O(n)O(n)O(n) 。
空间复杂度 : O(1)O(1)O(1) ，只使用常量级空间。

AC

致语

理解思路很重要！
欢迎读者在评论区留言，墨染看到就会回复的。

上一篇：MARKETS AND MARKET LOGIC——The Market‘s Principles (1)

下一篇：（二十四）Vue之props配置项

力扣(LeetCode)1759. 统计同构子字符串的数目(C++)

题目描述

双指针数学

名词解释

核心代码

AC

致语

相关内容

热门资讯