#3084

Medium

LeetCode Problem Workspace

Count Substrings Starting and Ending with Given Character

Given a string and a character, find the total number of substrings that start and end with that character.

Problem Statement

You are given a string s and a character c. Your task is to find the total number of substrings of s that both start and end with the character c.

For example, if s = "abada" and c = "a", the substrings that begin and end with 'a' are: "a", "aba", "abada", and others, which gives a total of 6 substrings.

Examples

Example 1

Input: s = "abada", c = "a"

Output: 6

Substrings starting and ending with "a" are: " a bada" , " aba da" , " abada " , "ab a da" , "ab ada " , "abad a " .

Example 2

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

Output: 6

There are a total of 6 substrings in s and all start and end with "z" .

Constraints

1 <= s.length <= 105
s and c consist only of lowercase English letters.

Solution Approach

Count Occurrences of Character

The first step is to count the number of times the character c appears in the string s. Let’s call this number m. The total substrings that start and end with c can be derived from these m occurrences.

Mathematical Approach

Once the count m is known, the total number of substrings is simply the number of ways to choose two positions from the m occurrences (including choosing the same position for substrings of length 1). This is calculated using the formula m * (m - 1) / 2 + m.

Optimizing with Simple Counting

To make the calculation efficient, we simply need to iterate through the string once to count m and then apply the formula. This ensures the solution works within the problem's constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the length of the string s, since we only need to count occurrences of the character c. The space complexity is O(1), as we only need a few variables for the counting process and final computation.

What Interviewers Usually Probe

Check if the candidate counts occurrences correctly and applies the mathematical formula properly.
Look for efficient handling of large strings, as the length can reach 10^5.
Assess if the candidate recognizes the need to avoid brute force approaches like checking all possible substrings.

Common Pitfalls or Variants

Common pitfalls

Forgetting to include substrings of length 1 in the calculation.
Confusing the mathematical formula for substring counting, especially how to handle the pairings of occurrences.
Overcomplicating the problem by trying to find substrings directly, instead of focusing on character occurrences.

Follow-up variants

Modify the problem to allow multiple characters instead of just one to be checked at the beginning and end.
Extend the problem to handle strings with upper and lowercase characters or other special characters.
Change the task to count substrings that start with c and end with a different character.

FAQ

How can I count substrings that start and end with a specific character?

Count the number of occurrences of the character in the string. The number of valid substrings can be calculated with the formula m * (m - 1) / 2 + m.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the string, because we only need to count the occurrences of the character.

What are the common mistakes in solving the Count Substrings Starting and Ending with Given Character problem?

Common mistakes include forgetting to include substrings of length 1, misapplying the formula for counting, or trying to check all substrings directly.

Can the solution be optimized further?

No, the solution is already optimal with O(n) time complexity for counting occurrences. It does not require checking all possible substrings.

How does the formula for counting substrings work?

The formula m * (m - 1) / 2 + m counts how many ways you can pick two positions from m occurrences and adds m for single-character substrings.

terminal

Solution

Solution 1: Mathematics

First, we can count the number of character $c$ in string $s$, denoted as $cnt$.

1

2

3

4

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

Continue Practicing

#3335 total characters in string after transformations i #3337 total characters in string after transformations ii #3443 maximum manhattan distance after k changes