题目描述
给你一个字符串 s
和一个字符 c
。返回在字符串 s
中并且以 c
字符开头和结尾的 非空子字符串 的总数。
样例
输入:s = "abada", c = "a"
输出:6
解释:以 "a" 开头和结尾的子字符串有:
"(a)bada"、"(aba)da"、"(abada)"、"ab(a)da"、"ab(ada)"、"abad(a)"。
输入:s = "zzz", c = "z"
输出:6
解释:字符串 s 中总共有 6 个子字符串,并且它们都以 "z" 开头和结尾。
限制
1 <= s.length <= 10^5
s
和c
均由小写英文字母组成。
算法
(思维题) $O(n)$
- 遍历字符串,求出字符串中等于
c
的字符个数 $cnt$。 - 注意到,符合要求的子串都是从字符串中任选两个等于
c
的字符(可以相同),构成的字符区间。 - 所以,答案为 $(cnt + 1) cnt / 2$。
时间复杂度
- 遍历字符串一次,时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
#define LL long long
class Solution {
public:
LL countSubstrings(string s, char c) {
const int n = s.size();
int cnt = 0;
for (int i = 0; i < n; i++)
if (s[i] == c)
++cnt;
return (LL)(cnt + 1) * cnt / 2;
}
};