Problem Statement in English

You’re given a string s consisting only of characters ‘a’, ‘b’, and ‘c’. You need to return the number of substrings that contain at least one occurrence of all three characters.

Approach

The idea is to use a sliding window approach to find all substrings that contain at least one occurrence of ‘a’, ‘b’, and ‘c’.

We will maintain a hashmap to keep track of the counts of each character in the current window. When the window contains all three characters, we can count the number of valid substrings that can be formed with the current right pointer by looking forwards.

We then shrink the window from the left until it no longer contains all three characters, and repeat the process.

And we’re done!

Solution in Python


class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        n = len(s)
        
        l = res = 0
        hm = defaultdict(int)

        for r, c in enumerate(s):
            hm[c] += 1

            while len(hm) == 3:
                res += n - r
                oc = s[l]
                hm[oc] -= 1

                if not hm[oc]: del hm[oc]

                l += 1

        return res

Complexity

  • Time: $O(n)$
    Since we are using a sliding window approach, the time complexity is linear.

  • Space: $O(1)$
    Since we are using a hashmap of size 3, the space complexity is constant.

Mistakes I Made

I completely botched the way of looking at the window and shrinking it. UGH!

And we are done.