Leetcode 1358 - Number of Substrings Containing All Three Characters

Understanding the problem

You are given a string s consisting of only ‘a’, ‘b’ and ‘c’ characters.

Return the number of substrings of s that contain all three characters ‘a’, ‘b’ and ‘c’.

Example:

Input: s = “abcabc”

Output: 10

Explanation: There are 10 substrings that contain all three characters: “abc”, “bca”, “cab”, “abc”, “bca”, “cab”, “abc”, “bca”, “cab” and “abc”.

Input: s = “aaacb”

Output: 3

Explanation: There are 3 substrings that contain all three characters: “aaacb”, “aacb” and “acb”.

Constraints:

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

Plan your solution

One approach to solve this problem is to use a sliding window.

We can start by initializing three variables a, b and c to 0. These variables will keep track of the number of occurrences of ‘a’, ‘b’ and ‘c’ characters in the current window.

We can also initialize a variable count to 0. This variable will keep track of the number of substrings of s that contain all three characters ‘a’, ‘b’ and ‘c’.

Then, we can initialize a variable window to an empty string. This variable will keep track of the current window.

Next, we can use a for loop to iterate over the elements of s and do the following:

• Add the current character to the window.
• Increment the count of the current character by 1.
• While the count of all three characters is greater than or equal to 1, do the following:
  • Remove the first character of the window.
  • Decrement the count of the removed character by 1.
  • Increment count by 1.

Finally, we return count.

Implement your solution

Now let’s implement the solution in Python.

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        # Initialize a, b, c and count
        a = b = c = count = 0
        # Initialize window
        window = ''
        
        # Iterate over elements of s
        for i in range(len(s)):
            # Add current character to the window
            window += s[i]
            # Increment the count of the current character by 1
            if s[i] == 'a':
                a += 1
            elif s[i] == 'b':
                b += 1
            elif s[i] == 'c':
                c += 1
            
            # If the count of all three characters is greater than or equal to 1, increment count by 1
            while a and b and c:
                # Remove the first character of the window
                window = window[1:]
                if window[0] == 'a':
                    a -= 1
                elif window[0] == 'b':
                    b -= 1
                elif window[0] == 'c':
                    c -= 1
                count += 1
        
        # Return count
        return count

Test your solution

Now we can test our solution with the same test cases:

s = "abcabc"
assert numberOfSubstrings(s) == 10

s = "aaacb"
assert numberOfSubstrings(s) == 3

s = "abc"
assert numberOfSubstrings(s) == 1

s = "abca"
assert numberOfSubstrings(s) == 3

s = "abcabcabc"
assert numberOfSubstrings(s) == 28

All the test cases pass, which means our solution is correct.

Related:

• permutation in string
• count complete tree nodes
• count negative numbers in a sorted matrix