Count Substrings Starting and Ending with Given Character Python/Java solution

Most implementations follow the same logic across languages. Iterate through the string, increment a counter when the target character appears, and add that counter to the result. This pattern translates directly to Python, Java, C++, JavaScript, and C# with O(n) time complexity.

What is the best approach for Count Substrings Starting and Ending with Given Character?

The optimal approach is a single-pass counting technique. Iterate through the string and keep a running count of how many times the target character has appeared. Each new occurrence adds that count to the answer. This runs in O(n) time and O(1) space and avoids generating substrings explicitly.

Is Count Substrings Starting and Ending with Given Character asked at Google/Amazon/Meta?

Substring counting and combinatorial string problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants often involve counting substrings with specific constraints, using prefix counts, hash maps, or mathematical observations.

What data structure is used in Count Substrings Starting and Ending with Given Character?

The optimal solution does not require complex data structures. It mainly uses a simple counter while iterating through the string. An alternative approach stores the indices of the target character in an array or list and applies a combinatorial formula.

What is the time complexity of Count Substrings Starting and Ending with Given Character?

The optimal solution runs in O(n) time where n is the length of the string. The algorithm scans the string once and performs constant-time operations for each character. Space complexity is O(1) for the counting approach or O(k) if you store indices of the character.

Description Hints 3 Solution Video 11:39

3084. Count Substrings Starting and Ending with Given Character

Q: Is Count Substrings Starting and Ending with Given Character easy or hard?

The problem is typically considered easy to medium difficulty. The implementation is simple once you recognize the counting pattern, but the key challenge is spotting the combinatorial insight that avoids brute-force substring generation.

Q: How to solve Count Substrings Starting and Ending with Given Character in O(n)?

Traverse the string and maintain a variable that counts how many times the target character has appeared. Whenever the current character equals the target, increment the counter and add it to the result. Each occurrence forms substrings with all previous occurrences, giving the correct total in linear time.

Medium50.5% acceptance

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 <= 10⁵
s and c consist only of lowercase English letters.

Topics

Hints open one at a time

Hint 1

Count the number of characters 'c' in string s, let’s call it m.

Hint 2

We can select 2 numbers i and j such that i <= j are the start and end indices of substring. Note that i and j can be the same.

Hint 3

The answer is m * (m + 1) / 2.

11:39

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def countSubstrings(self, s: str, c: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"abada"
"a"

Input

"zzz"
"z"

Your code is saved on this device.Solution