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 with Only One Distinct Letter

Number: 1131

Difficulty: Easy

Paid? Yes

Companies: Virtu Financial

Problem Description

Given a string s, return the number of substrings that have only one distinct letter.

Key Insights

  • The problem asks for counting substrings that consist of a single repeating letter.
  • Instead of checking each substring individually, notice that any contiguous group of the same character contributes multiple valid substrings.
  • For a group with n same characters, the number of valid substrings is given by n*(n+1)/2.
  • The overall solution is simply to traverse the string, group the same consecutive characters, and sum up the counts based on the above formula.

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), as we use a fixed amount of extra space.

Solution

The solution involves iterating through the string while counting how many times the same character appears consecutively. Every time the character changes (or at the end of the string), we calculate the number of substrings using the formula n*(n+1)/2 for the current group. We then reset the count and continue with the next group. This approach uses simple arithmetic and a single loop through the string.

Code Solutions

# Python solution with line-by-line comments

def countLetters(s: str) -> int:
    # Initialize total count of substrings and a counter for the current group
    count = 0
    current_count = 1  # Count at least one occurrence (the first letter)
    n = len(s)
    
    # Loop through the string starting from the second character
    for i in range(1, n):
        if s[i] == s[i - 1]:
            # Same character as previous, so increase the current group count
            current_count += 1
        else:
            # New character encountered, compute substring count for the current group
            count += current_count * (current_count + 1) // 2
            # Reset the current group count for the new character
            current_count = 1
            
    # Add the count for the final group of characters
    count += current_count * (current_count + 1) // 2
    return count

# Example usage:
print(countLetters("aaaba"))  # Expected output: 8
← Back to All Questions