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

Substrings That Begin and End With the Same Letter

Number: 2225

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given a 0-indexed string s consisting only of lowercase English letters, count the number of substrings (contiguous non-empty sequences) that begin and end with the same letter. Each individual character is considered a valid substring.

Key Insights

  • Every single character is a valid substring (counts as 1).
  • For any letter that appears f times, the number of substrings that start and end with that letter is f * (f + 1) / 2.
  • Instead of checking all possible substrings, count the frequency of each letter and use the mathematical formula above.
  • This approach leverages counting and simple arithmetic instead of nested loops.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, since we traverse the string once. Space Complexity: O(1), because we only need an array or dictionary of fixed size (26 for lowercase letters).

Solution

We solve the problem by:

  1. Iterating over the string to count the frequency of each letter.
  2. For each letter with frequency f, adding f * (f + 1) / 2 to the result.
  3. Returning the sum of these values. The key is to note that each letter at a given frequency contributes both its individual occurrences (as 1-length substrings) and all pairs of positions that form valid substrings.

Code Solutions

# Define a function to count valid substrings
def count_substrings(s):
    # Create a dictionary to record frequency of each character
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1  # Increment the count for the character
    count = 0
    # For each character frequency, add the number of substrings using the formula f*(f+1)/2
    for f in freq.values():
        count += f * (f + 1) // 2
    return count

# Example usage:
s = "abcba"
print(count_substrings(s))  # Expected Output: 7
← Back to All Questions