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 <= 105s and c consist only of lowercase English letters.Problem Overview: You are given a string s and a character c. The task is to count how many substrings start and end with c. Any substring is valid as long as its first and last characters match the given character.
The key observation: if the character c appears k times in the string, every occurrence can pair with itself or any later occurrence to form a valid substring. That turns the problem into a simple counting problem rather than generating substrings explicitly.
Approach 1: Two-Pointers and Counting (Time: O(n), Space: O(1))
Traverse the string once and keep a counter of how many times the character c has appeared so far. Every time you encounter c, increment the counter and add its value to the result. This works because each new occurrence can form substrings with all previous occurrences, including itself. Instead of maintaining explicit two pointers, the running count implicitly represents all possible starting points for substrings ending at the current index. This approach relies on simple iteration and arithmetic, making it the most efficient solution for large inputs.
Approach 2: Precomputing Positions of Character (Time: O(n), Space: O(k))
First iterate through the string and store the indices where c appears in a list. If there are k such positions, the number of valid substrings equals k * (k + 1) / 2. Each occurrence can be the start of a substring that ends at itself or any later occurrence. This approach separates the discovery of relevant characters from the counting step, which can make the logic easier to reason about when analyzing substring boundaries.
Both approaches rely on the same mathematical insight: counting combinations of positions rather than constructing substrings. Problems like this frequently appear in string processing and counting patterns, and the formula-based reasoning comes from basic math combinatorics.
Recommended for interviews: The single-pass counting approach is what most interviewers expect. It demonstrates that you recognized the combinatorial pattern and avoided unnecessary substring generation. Showing the mathematical reasoning behind k * (k + 1) / 2 signals strong problem‑solving intuition.
In this approach, we use the two-pointers method to find positions where the substring starts and ends with the character 'c'. We have a simple count of all such occurrences using combinations.
We iterate through the string, and every time we see the character 'c', we increment a counter 'prevCount' representing the number of 'c' encountered so far. This counter is added to a global 'count' which keeps track of all valid substrings ending at the current position. This way, we consider all substrings formed with the current 'c' as an endpoint.
Time Complexity: O(n), Space Complexity: O(1)
This approach involves precomputing all positions of the character 'c' and then using combinations of these positions to calculate the number of valid substrings.
This method involves first storing all positions of the character 'c' in an array. For each of these positions (let's call one of them start), there are valid substrings with this position as the start for every subsequent position in the list. So, we just need to consider combinations of start-end pairs.
Time Complexity: O(n), Space Complexity: O(n)
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).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Two-Pointers and Counting | Time Complexity: O(n), Space Complexity: O(1) |
| Approach 2: Precomputing Positions of Character | Time Complexity: O(n), Space Complexity: O(n) |
| Mathematics | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointers and Counting | O(n) | O(1) | Best general solution. Single pass with constant memory. |
| Precomputing Positions of Character | O(n) | O(k) | Useful when you want explicit indices of the character for further processing. |
Count Substrings Starting and Ending with Given Character | Leetcode 3084 | codestorywithMIK • codestorywithMIK • 4,812 views views
Watch 9 more video solutions →Practice Count Substrings Starting and Ending with Given Character with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor