Count Substrings Starting and Ending with Given Character Solution
Count Substrings Starting and Ending with Given Character solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Count Substrings Starting and Ending with Given Character is a medium coding problem on strings, math and counting, asked in Amazon, Google and Oracle interviews.
- Difficulty: Medium
- Topics: Strings, Math, Counting
- Asked at: Amazon, Google, Oracle
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^4s and c consist only of lowercase English letters.
Hints for Count Substrings Starting and Ending with Given Character
Hint 1
A qualifying substring is determined entirely by which occurrence of
cit starts at and which it ends at.Hint 2
If
coccursmtimes, how many ordered pairs (start, end) with start ≤ end are there?Hint 3
The answer is
m * (m + 1) / 2— no substring is ever built.
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
- Count how many times
cappears ins. - 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) // 2Java
public static int countSubstrings(String s, String c) {
long m = 0;
char target = c.charAt(0);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == target) m++;
}
return (int) (m * (m + 1) / 2);
}C++
int countSubstrings(string s, string c) {
long long m = 0;
char target = c[0];
for (char ch : s) {
if (ch == target) m++;
}
return (int) (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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings