3084. Count Substrings Starting and Ending with Given Character
Description
You are given a string s
and a character c
. Return the total number of substrings of s
that start and end with c
.
Example 1:
Input: s = "abada", c = "a"
Output: 6
Explanation: Substrings starting and ending with "a"
are: "abada"
, "abada"
, "abada"
, "abada"
, "abada"
, "abada"
.
Example 2:
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 <= 105
s
andc
consist only of lowercase English letters.
Solutions
Solution 1: Mathematics
First, we can count the number of character $c$ in string $s$, denoted as $cnt$.
Each character $c$ can form a substring on its own, so there are $cnt$ substrings that meet the condition. Each character $c$ can form a substring with other $c$ characters, so there are $\frac{cnt \times (cnt - 1)}{2}$ substrings that meet the condition.
Therefore, the answer is $cnt + \frac{cnt \times (cnt - 1)}{2}$.
The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)$.
1 2 3 4 |
|
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 |
|
1 2 3 4 |
|
1 2 3 4 |
|