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

Number of Substrings Containing All Three Characters

Number: 1460

Difficulty: Medium

Paid? No

Companies: Google, Meta, Amazon, Bloomberg, TikTok, DE Shaw

Problem Description

Given a string s that consists only of characters a, b, and c, return the number of substrings that contain at least one occurrence of each of these characters.

Key Insights

  • Use the sliding window technique to efficiently capture a valid window containing at least one a, one b, and one c.
  • For every valid window, all substrings ending after the right pointer are valid, so you can count them in constant time.
  • Shrinking the window from the left while maintaining validity helps in counting all possible substrings without reprocessing the entire string.

Space and Time Complexity

Time Complexity: O(n) – Each character is processed at most twice (once when expanding the window and once when contracting it).
Space Complexity: O(1) – Only a fixed-size dictionary (or array) is used to count occurrences of a, b, and c.

Solution

The solution uses a sliding window approach with two pointers (left and right). We expand the right pointer to include new characters while maintaining a count of each character. Once the window is valid (contains at least one a, one b, and one c), we know that any substring starting from the left index and ending at any index from right to the end of the string is valid. Therefore, we add (n - right) to our result, where n is the length of the string. We then shrink the window from the left to explore new windows. This ensures that we count each valid substring exactly once.

Code Solutions

# Python solution with line-by-line comments

def numberOfSubstrings(s: str) -> int:
    # Initialize dictionary to count occurrences of 'a', 'b', and 'c'
    count = {'a': 0, 'b': 0, 'c': 0}
    n = len(s)
    result = 0
    left = 0

    # Iterate over each character with right pointer
    for right in range(n):
        # Increment the count for the current character
        count[s[right]] += 1
        
        # Check if the current window is valid (each character appears at least once)
        while count['a'] > 0 and count['b'] > 0 and count['c'] > 0:
            # All substrings starting from left and ending from right to n-1 are valid
            result += (n - right)
            # Move left pointer to try and find a smaller valid window
            count[s[left]] -= 1
            left += 1
    return result

# Example usage:
# print(numberOfSubstrings("abcabc"))
← Back to All Questions