Number of Substrings Containing All Three Characters

main.md

Question

Approach

I use a sliding window approach to count substrings containing at least one 'a', 'b', and 'c'. I expand the window to include characters until all three are present. Then, I count all possible substrings ending at right and reduce the window from left.

Implementation

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        count = {"a": 0, "b": 0, "c": 0}
        left = 0
        total = 0
        
        for right in range(len(s)):
            count[s[right]] += 1
            
            while all(count[char] > 0 for char in "abc"):
                total += len(s) - right
                count[s[left]] -= 1
                left += 1
        
        return total

Complexities

• Time: O(n)
• Space: O(1)