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

Number of Substrings Containing All Three Characters

Difficulty: Medium

Problem Description

Given a string s consisting only of characters a, b, and c. Return the number of substrings containing at least one occurrence of all these characters a, b, and c.

Key Insights

  • A substring must contain at least one 'a', one 'b', and one 'c' to be counted.
  • The problem can be solved using a sliding window approach, which efficiently keeps track of character counts.
  • We can use a hash table (or a simple array) to count occurrences of 'a', 'b', and 'c' within the current window.
  • Once we have a valid window containing all three characters, we can count how many substrings can be formed by extending the right end of the window.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (since we only use a fixed-size array to count characters)

Solution

To solve this problem, we can use a sliding window approach. We maintain a window that expands by moving the right pointer and contracts by moving the left pointer. As we expand the window, we update the counts of 'a', 'b', and 'c'. When the window contains at least one of each character, we can count all possible substrings that start from the left pointer and end at the right pointer, then move the left pointer forward to explore new potential substrings.

Code Solutions

def numberOfSubstrings(s: str) -> int:
    count = {'a': 0, 'b': 0, 'c': 0}
    left = 0
    result = 0

    for right in range(len(s)):
        count[s[right]] += 1
        
        while all(count[c] > 0 for c in 'abc'):
            result += len(s) - right
            count[s[left]] -= 1
            left += 1

    return result
← Back to All Questions