1358.Number_of_Substrings_Containing_All_Three_Characters(Medium).md

1358. Number of Substrings Containing All Three Characters (Medium)

Date and Time: Mar 10, 2025, 22:58 (EST)

Link: https://leetcode.com/problems/number-of-substrings-containing-all-three-characters

Question:

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.

Example 1:

Input: s = "abcabc"
Output: 10
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (again).

Example 2:

Input: s = "aaacb"
Output: 3
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "aaacb", "aacb" and "acb".

Example 3:

Input: s = "abc"
Output: 1

Constraints:

• 3 <= s.length <= 5 x 10^4

• s only consists of a, b or c characters.

Walk-through:

1. Use two ptrs to maintain a sliding window. We start updating the ptrs to include a valid sliding window. Then we count the distance from current r ptr to the end of s, which means how many more substrings we can form.

2. After that, advance the l ptr to make the sliding window to be invalid. Then, expand the r ptr until the sliding window is valid again. Update ans with the extra chars we can add.

Python Solution:

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        # Maintain a valid sliding window which contains a,b, and c at least once.
        # When we have one valid sliding window, count how many extra chars we can add until the end of s
        # After we count the extra chars, start shrinking the left ptr until sliding window is invalid, then expand the right ptr again until sliding window is valid.

        # TC: O(n^2), n=len(s), SC: O(1)
        hashmap = {}     # Keep track of 'a', 'b', 'c'
        l, r = 0, 0
        ans = 0
        while r < len(s):
            # Update till sliding window is valid
            if len(hashmap) < 3:
                hashmap[s[r]] = hashmap.get(s[r], 0)+1
            r += 1
            # Shrink the left ptr
            while len(hashmap) == 3:
                ans += len(s)-r+1
                if hashmap[s[l]] == 1:
                    del hashmap[s[l]]
                else:
                    hashmap[s[l]] -= 1
                l += 1
        return ans

Time Complexity: $O(n)$, use two ptrs
Space Complexity: $O(1)$