Count Substrings Starting and Ending with Given Character - Video Solutions

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.