Count Substrings Starting and Ending with Given Character — Medium Problem & Solution

Problem statement

Return the number of substrings of s that both start and end with the character c. A single occurrence of c counts as a substring of length one.

Example 1

Input: s = "codekairo", c = "o"
Output: 3
Explanation: The two `o`s give `o`, `o` and `odekairo`.

Example 2

Input: s = "abada", c = "a"
Output: 6
Explanation: Three `a`s give 3 + 2 + 1 = 6 substrings.

Example 3

Input: s = "zzz", c = "z"
Output: 6

Constraints

• 1 <= s.length <= 10^4
• s and c consist only of lowercase English letters.

How to solve Count Substrings Starting and Ending with Given Character

Count the occurrences of c. Every qualifying substring corresponds to a pair of occurrences — one for the start, one for the end, with the start no later than the end — so the answer is m choose 2 plus the m single-character substrings, which is m(m+1)/2.

Approach

1. Count how many times c appears in s.
2. Return m * (m + 1) / 2.

Why it works

Everything between the two chosen occurrences is irrelevant — the substring is fixed once its endpoints are. That turns an apparent O(n²) enumeration into a single count, which is what the 10⁴ bound is really testing. The + m term is easy to lose: an occurrence paired with itself is a valid length-one substring.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Length-one substrings count — do not use m * (m - 1) / 2.
• Enumerating substrings directly is O(n²) and far too slow at the upper bound.
• m * (m + 1) is always even, so the integer division is exact.

Reference solution

Python

def countSubstrings(s: str, c: str) -> int:
    m = s.count(c)
    return m * (m + 1) // 2

JavaScript

var countSubstrings = function(s, c) {
    var m = 0;
    for (var i = 0; i < s.length; i++) if (s.charAt(i) === c) m++;
    return m * (m + 1) / 2;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Find the Winner of the Circular Game Medium
• Stone Game VII Medium
• Number of Ways to Divide a Long Corridor Medium
• Count Ways to Group Overlapping Ranges Medium
• Count Number of Ways to Place Houses Medium
• Count Number of Texts Medium