3084. Count Substrings Starting and Ending with Given Character

MediumMathStringCounting

Problem Description

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.

A substring is a contiguous sequence of characters within the string. For example, if s = "abcab" and c = 'a', the valid substrings would be:

"a" (first character alone)
"a" (last character alone)
"abca" (from first 'a' to second 'a')

The solution uses a mathematical approach. If there are cnt occurrences of character c in the string:

Each occurrence of c can form a substring by itself, giving us cnt single-character substrings
Any two occurrences of c can form a substring that starts with one and ends with the other

Since we need to count all possible pairs of c characters (including using the same character as both start and end for single-character substrings), the total count is cnt + cnt * (cnt - 1) / 2, where:

cnt represents the single-character substrings
cnt * (cnt - 1) / 2 represents all possible combinations of choosing 2 different positions of c to form longer substrings

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is recognizing that any substring starting and ending with character c is uniquely determined by choosing two positions where c appears (or the same position for single-character substrings).

Let's think about this step by step. If we have cnt occurrences of character c in the string, we need to count:

How many ways can we pick one c to form a single-character substring? That's simply cnt ways.
How many ways can we pick two different c positions to form longer substrings? This is a combination problem - choosing 2 positions from cnt positions, which gives us C(cnt, 2) = cnt * (cnt - 1) / 2.

For example, if s = "abcac" and c = 'a', we have two as at positions 0 and 3. The valid substrings are:

"a" at position 0 (single character)
"a" at position 3 (single character)
"abca" from position 0 to 3 (using both as)

This gives us 2 + 1 = 3 total substrings, which matches our formula: 2 + 2 * 1 / 2 = 3.

The beauty of this approach is that we don't need to actually generate or check all substrings. We just count the occurrences of c and apply the combinatorial formula. This transforms what could be an O(n²) substring enumeration problem into an O(n) counting problem.

Learn more about Math patterns.

Solution Approach

The implementation is straightforward and efficient, requiring only a single pass through the string:

Count occurrences of character c: Use Python's built-in count() method to find how many times character c appears in string s. Store this value in variable cnt.
Apply the mathematical formula: Calculate the total number of valid substrings using the formula cnt + cnt * (cnt - 1) // 2, where:
- cnt represents substrings consisting of a single character c
- cnt * (cnt - 1) // 2 represents all possible substrings formed by choosing any two different positions of c as start and end points
- We use integer division // since we're dealing with counts (which must be whole numbers)

The algorithm leverages the mathematical insight that each valid substring is uniquely determined by its starting and ending positions (both containing character c). Instead of generating all possible substrings and checking each one, we directly compute the count using combinatorics.

Time Complexity: O(n) where n is the length of the string, as count() needs to scan through the entire string once.

Space Complexity: O(1) as we only use a constant amount of extra space to store the count.

The elegance of this solution lies in transforming a potentially complex string manipulation problem into a simple counting and arithmetic calculation.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example with s = "abacad" and c = 'a'.

Step 1: Count occurrences of character 'a'

Scan through the string: "abacad"
We find 'a' at positions 0, 2, and 4
So cnt = 3

Step 2: Apply the formula

Formula: cnt + cnt * (cnt - 1) // 2
Substitute: 3 + 3 * (3 - 1) // 2
Calculate: 3 + 3 * 2 // 2
Simplify: 3 + 6 // 2
Result: 3 + 3 = 6

Step 3: Verify our answer Let's list all valid substrings that start and end with 'a':

"a" (position 0 alone) - single character substring
"aba" (position 0 to 2) - starts at first 'a', ends at second 'a'
"abaca" (position 0 to 4) - starts at first 'a', ends at third 'a'
"a" (position 2 alone) - single character substring
"aca" (position 2 to 4) - starts at second 'a', ends at third 'a'
"a" (position 4 alone) - single character substring

We have exactly 6 valid substrings, confirming our formula works correctly!

Notice how we have:

3 single-character substrings (one for each 'a')
3 multi-character substrings (one for each unique pair of 'a' positions: (0,2), (0,4), (2,4))

This matches our formula's breakdown: 3 (single characters) + 3 (pairs) = 6 total.

Solution Implementation

1class Solution:
2    def countSubstrings(self, s: str, c: str) -> int:
3        # Count the total occurrences of character c in string s
4        count = s.count(c)
5      
6        # Calculate total substrings that start and end with character c
7        # This includes:
8        # - Single character substrings (each occurrence of c): count
9        # - Multi-character substrings (pairs of c): count * (count - 1) / 2
10        # Using the combination formula C(n, 2) = n * (n - 1) / 2 for pairs
11        # Total = count + C(count, 2)
12        total_substrings = count + count * (count - 1) // 2
13      
14        return total_substrings
15

1class Solution {
2    public long countSubstrings(String s, char c) {
3        // Count the total occurrences of character c in string s
4        long count = s.chars().filter(ch -> ch == c).count();
5      
6        // Calculate total substrings containing only character c
7        // For n occurrences of c:
8        // - Single character substrings: count
9        // - Multiple character substrings: count * (count - 1) / 2 (combination formula)
10        // Total = count + count * (count - 1) / 2
11        return count + count * (count - 1) / 2;
12    }
13}
14

1class Solution {
2public:
3    long long countSubstrings(string s, char c) {
4        // Count the total occurrences of character c in string s
5        long long count = 0;
6        for (char ch : s) {
7            if (ch == c) {
8                count++;
9            }
10        }
11      
12        // Calculate total substrings containing only character c
13        // Each occurrence of c forms 1 substring of length 1
14        // Any pair of occurrences forms additional substrings
15        // Formula: count + count * (count - 1) / 2
16        // This equals count * (count + 1) / 2 (sum of first count natural numbers)
17        return count + count * (count - 1) / 2;
18    }
19};
20

1/**
2 * Counts the number of substrings that start and end with character c
3 * @param s - The input string to search within
4 * @param c - The target character that substrings must start and end with
5 * @returns The total count of valid substrings
6 */
7function countSubstrings(s: string, c: string): number {
8    // Count occurrences of character c in the string
9    const occurrenceCount: number = s.split('').filter((char: string) => char === c).length;
10  
11    // Calculate total substrings using the formula: n + n*(n-1)/2
12    // where n is the count of character c
13    // This formula accounts for:
14    // - n single character substrings (each occurrence of c itself)
15    // - n*(n-1)/2 substrings between different occurrences of c
16    const totalSubstrings: number = occurrenceCount + Math.floor((occurrenceCount * (occurrenceCount - 1)) / 2);
17  
18    return totalSubstrings;
19}
20

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. This is because the s.count(c) method needs to traverse the entire string once to count all occurrences of character c. The subsequent arithmetic operations (cnt * (cnt - 1) // 2) are performed in constant time O(1).

The space complexity is O(1). The algorithm only uses a constant amount of extra space to store the variable cnt (an integer), regardless of the input size. No additional data structures that scale with the input are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Large Inputs

When cnt is very large, calculating cnt * (cnt - 1) might cause integer overflow in languages with fixed integer sizes. For example, if cnt = 100,000, then cnt * (cnt - 1) = 9,999,900,000.

Solution: In Python, this isn't an issue due to arbitrary precision integers, but in other languages like Java or C++, use long/long long data types or check for potential overflow before multiplication.

2. Using Float Division Instead of Integer Division

Writing cnt * (cnt - 1) / 2 instead of cnt * (cnt - 1) // 2 would return a float, which is unnecessary and could cause issues if the result needs to be an integer.

Solution: Always use integer division // when dealing with counting problems to ensure the result is an integer.

3. Misunderstanding the Formula

Developers might incorrectly think the formula should be cnt * (cnt + 1) // 2 (sum of first n natural numbers) instead of cnt + cnt * (cnt - 1) // 2.

Solution: Remember that:

Single character substrings = cnt (each occurrence of c by itself)
Multi-character substrings = C(cnt, 2) = cnt * (cnt - 1) // 2 (choosing 2 different positions)
Total = cnt + cnt * (cnt - 1) // 2 = cnt * (cnt + 1) // 2

4. Not Handling Edge Cases

Failing to consider when c doesn't appear in the string at all (cnt = 0).

Solution: The formula naturally handles this case (returns 0), but it's good practice to explicitly verify:

if cnt == 0:
    return 0

5. Case Sensitivity Issues

If the problem requires case-insensitive matching but the implementation uses case-sensitive counting.

Solution: Clarify requirements and if needed, convert both the string and character to the same case:

count = s.lower().count(c.lower())

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Is the following code DFS or BFS?

void search(Node root) {
  if (!root) return;
  visit(root);
  root.visited = true;
  for (Node node in root.adjacent) {
    if (!node.visited) {
      search(node);
    }
  }
}

Depth First Search

Breadth First Search

I don't know