3084. Count Substrings Starting and Ending with Given Character

MediumMathStringCounting

Problem Description

You are given a string s and a character c. The task is to determine the total number of non-empty substrings of s that both start and end with the character c.

Intuition

To solve this problem, the key observation is understanding the nature of substrings that start and end with the same character. First, count how many times the character c appears in the string s. Let's call this count cnt.

Each occurrence of c can form a substring by itself, contributing cnt substrings. Beyond that, each pair of this character can form additional substrings. If we choose two positions where c appears, all substrings starting at the first and ending at the second will satisfy the condition. There are cnt * (cnt - 1) / 2 possible ways to select these starting and ending positions from cnt positions.

Therefore, the total number of substrings is given by the formula:

cnt single-character substrings, plus
cnt * (cnt - 1) / 2 multi-character substrings.

This mathematical approach efficiently calculates the total desired substrings.

Learn more about Math patterns.

Solution Approach

The solution leverages a simple mathematical formula to efficiently calculate the number of substrings that start and end with the character c.

Count Occurrences: First, we count the number of times the character c appears in the string s. This is achieved using Python's built-in count method: cnt = s.count(c).
Calculate Substrings:
- Each occurrence of c forms a substring of length 1. Thus, there are cnt such single-character substrings.
- For substrings longer than one character, consider pairs of positions where c appears. Each such pair defines a substring. The mathematical formula for selecting two positions from cnt occurrences is given by the combination formula cnt * (cnt - 1) / 2.
Combine Results: Add the two results:
- cnt for the single-character substrings.
- cnt * (cnt - 1) / 2 for the multi-character substrings.

Using the formula, the function returns cnt + cnt * (cnt - 1) // 2, providing the total count efficiently, without the need to explicitly enumerate substrings.

Implementing this in code:

class Solution:
    def countSubstrings(self, s: str, c: str) -> int:
        cnt = s.count(c)  # Count occurrences of c in s
        return cnt + cnt * (cnt - 1) // 2  # Calculate total number of valid substrings

This approach ensures optimal performance by avoiding unnecessary iterations and uses constant space.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach.

Example:

Let s = "abcaacaa" and c = "a".

Step 1: Count Occurrences

First, determine how many times c appears in s.
- In s = "abcaacaa", the character a appears 5 times.
- Thus, cnt = 5.

Step 2: Calculate Substrings

Single-character substrings:
- Each occurrence of a can be a substring itself. Therefore, there are 5 single-character substrings.
Multi-character substrings:
- For substrings greater than one character, identify the number of ways to choose two positions out of the 5 occurrences.
- Using the combination formula, cnt * (cnt - 1) / 2, the calculation is:
  - 5 * (5 - 1) / 2 = 10 multi-character substrings.

Step 3: Combine Results

Add the single-character and multi-character substring counts:
- Total substrings = 5 (single-character) + 10 (multi-character) = 15.

Therefore, there are 15 non-empty substrings in the string s = "abcaacaa" that start and end with the character a.

This method efficiently computes the result with minimal computation by leveraging the mathematical formula, ensuring optimal performance.

Solution Implementation

1class Solution:
2    def countSubstrings(self, s: str, c: str) -> int:
3        # Count the number of occurrences of the character c in the string s
4        count = s.count(c)
5      
6        # Calculate the number of substrings that consist solely of the character c
7        # This includes single character substrings (count)
8        # and combinations of two or more c's, which can be derived by the formula: count * (count - 1) // 2
9        # The formula is derived from combinations (n choose 2) to select pairs of positions
10        # where c occurs, which can form a substring consisting entirely of c.
11        return count + count * (count - 1) // 2
12

1class Solution {
2    public long countSubstrings(String s, char c) {
3        // Count the number of occurrences of the character 'c' in the string 's'
4        long count = s.chars().filter(ch -> ch == c).count();
5      
6        // Calculate the total number of substrings containing at least one 'c'
7        // Each occurrence of 'c' can be treated as a single-character substring
8        // Additionally, choose pairs of those occurrences to form more substrings
9        // Total substrings = single occurrences + combinations of two occurrences
10        long substringsCount = count + count * (count - 1) / 2;
11      
12        return substringsCount;
13    }
14}
15

1class Solution {
2public:
3    long long countSubstrings(string s, char c) {
4        // Count the occurrences of character 'c' in the string 's'
5        long long count = std::count(s.begin(), s.end(), c);
6      
7        // Calculate the total number of substrings containing at least one occurrence of 'c'
8        // The formula is count + count * (count - 1) / 2 which represents
9        // the number of single character substrings (count itself) plus
10        // the number of pairwise combinations of 'c' (combinatorial way to calculate non-empty substrings)
11        return count + count * (count - 1) / 2;
12    }
13};
14

1// Function to count the number of substrings in s that contain the character c.
2function countSubstrings(s: string, c: string): number {
3    // Convert the string into an array of characters and filter to count occurrences of c.
4    const countC = s.split('').filter(ch => ch === c).length;
5
6    // Calculate the total number of substrings containing at least one c.
7    // This includes individual occurrences (countC) and combinations (pairs, triplets, etc.).
8    const totalCount = countC + Math.floor((countC * (countC - 1)) / 2);
9
10    // Return the calculated total count.
11    return totalCount;
12}
13

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the string s. This is because the method s.count(c) is called once, which traverses the string s to count occurrences of the character c.

The space complexity is O(1), as the algorithm uses a constant amount of extra space. The only variables used are cnt, which stores an integer count, and a constant amount of temporary space required for arithmetic operations.

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

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