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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Substrings Starting and Ending with Given Character

Number: 3337

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a string s and a character c, determine the total number of non-empty substrings of s that start and end with the character c.

Key Insights

  • Instead of generating all substrings (which would be inefficient), count how many times c occurs in the string.
  • Every occurrence can serve as a starting or ending point, and the total number of valid substrings can be computed using combinations.
  • The formula used is: if the character c appears n times, then the number of valid substrings is n * (n + 1) / 2. This formula accounts for both the substrings of length 1 (individual characters) and longer substrings.

Space and Time Complexity

Time Complexity: O(n), where n is the length of s (we iterate through the string once).
Space Complexity: O(1) (only a constant amount of extra space is used beyond the input).

Solution

The solution consists of a single pass to count the occurrences of the given character c in the input string s. Once n (the count of c) is obtained, the total number of substrings starting and ending with c is computed using the formula n * (n + 1) / 2. This approach leverages combinatorial counting instead of iterating over all possible substrings, ensuring the solution is efficient even for large inputs.

Code Solutions

# Python solution to count substrings starting and ending with a given character.

def count_substrings(s, c):
    # Count the number of occurrences of character c in s
    count = s.count(c)
    # Calculate and return the total substrings using the arithmetic formula
    return count * (count + 1) // 2

# Example usage:
if __name__ == "__main__":
    s = "abada"
    c = "a"
    print(count_substrings(s, c))  # Expected output: 6
← Back to All Questions