We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Substrings Starting and Ending with Given Character

Difficulty: Medium

Problem Description

You are given a string s and a character c. Return the total number of substrings of s that start and end with c.

Key Insights

  • A substring is defined as a contiguous sequence of characters within a string.
  • To find substrings that start and end with a specific character, we need to identify all occurrences of that character in the string.
  • The number of valid substrings can be calculated using the positions of these occurrences.
  • If there are n occurrences of the character c, the total number of substrings that can be formed is given by the formula: n * (n + 1) / 2.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s, since we may need to traverse the string once to count occurrences. Space Complexity: O(1), as we are using a constant amount of extra space.

Solution

To solve the problem, we can follow these steps:

  1. Initialize a count variable to track the occurrences of the character c in the string.
  2. Traverse the string and increment the count each time we encounter c.
  3. Use the formula n * (n + 1) / 2 to compute the total number of substrings that can be formed with these occurrences.

This approach ensures that we efficiently count the required substrings without generating them explicitly.

Code Solutions

def count_substrings(s: str, c: str) -> int:
    count = 0
    total_substrings = 0
    
    # Count the occurrences of character c in the string s
    for char in s:
        if char == c:
            count += 1
    
    # Calculate the total substrings using the formula
    total_substrings = count * (count + 1) // 2
    return total_substrings
← Back to All Questions