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.

1. 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).

2. 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.

3. 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.

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

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.