Problem#
You are given a string s
and a character c
. Return _the total number of substrings of _s
that start and end with c
.
Examples#
Example 1#
1
2
3
4
5
6
7
8
Input: s = "abada" , c = "a"
Output: 6
Explanation: Substrings starting and ending with `"a"` are: `"**_a_**
bada"` , `"_**aba**_ da"` , `"_**abada**_ "` , `"ab _**a**_ da"` , `"ab _**ada**_
"` , `"abad _**a**_ "` .
Example 2#
1
2
3
4
5
6
7
Input: s = "zzz" , c = "z"
Output: 6
Explanation: There are a total of `6` substrings in `s` and all start and
end with `"z"` .
Constraints#
1 <= s.length <= 10^5
s
and c
consist only of lowercase English letters.
Solution#
Method 1 – Counting Occurrences#
Intuition#
Every substring that starts and ends with the given character c
can be uniquely identified by picking two indices where c
occurs (possibly the same index). The number of such substrings is the number of ways to choose a start and end position among all positions where c
appears, including single-character substrings.
Approach#
Count the number of times c
appears in the string s
(let’s call it cnt
).
The number of substrings that start and end with c
is cnt * (cnt + 1) // 2
.
This is because for each pair of positions (i, j) with i <= j and s[i] == s[j] == c, the substring s[i:j+1] starts and ends with c
.
Return this value.
Code#
Cpp
Go
Java
Kotlin
Python
Rust
Typescript
1
2
3
4
5
6
7
8
class Solution {
public :
long long countSubstrings(string s, char c) {
long long cnt = 0 ;
for (char ch : s) if (ch == c) cnt++ ;
return cnt * (cnt + 1 ) / 2 ;
}
};
1
2
3
4
5
6
7
8
9
10
type Solution struct {}
func (Solution ) CountSubstrings (s string , c byte ) int64 {
var cnt int64
for i := 0 ; i < len(s ); i ++ {
if s [i ] == c {
cnt ++
}
}
return cnt * (cnt + 1 ) / 2
}
1
2
3
4
5
6
7
class Solution {
public long countSubstrings (String s, char c) {
long cnt = 0;
for (char ch : s.toCharArray ()) if (ch == c) cnt++ ;
return cnt * (cnt + 1) / 2;
}
}
1
2
3
4
5
6
class Solution {
fun countSubstrings (s: String, c: Char): Long {
val cnt = s.count { it == c }.toLong()
return cnt * (cnt + 1 ) / 2
}
}
1
2
3
4
class Solution :
def countSubstrings (self, s: str, c: str) -> int:
cnt = s. count(c)
return cnt * (cnt + 1 ) // 2
1
2
3
4
5
6
impl Solution {
pub fn count_substrings (s: String, c: char ) -> i64 {
let cnt = s.chars().filter(|& ch| ch == c).count() as i64 ;
cnt * (cnt + 1 ) / 2
}
}
1
2
3
4
5
6
class Solution {
countSubstrings (s : string , c : string ): number {
const cnt = s .split ('' ).filter (x => x === c ).length ;
return (cnt * (cnt + 1 )) / 2 ;
}
}
Complexity#
⏰ Time complexity: O(n)
, where n is the length of the string, since we scan the string once.
🧺 Space complexity: O(1)
, only a counter is used.