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

Related Posts

• Leetcode 424 - Longest Repeating Character Replacement
• Two Sum and Its Variants
• Leetcode 1004 - Max Consecutive Ones III
• Leetcode 222 - Count Complete Tree Nodes
• Leetcode 1027 - Longest Arithmetic Subsequence
• Question 1299 on leetcode
• Leetcode 240 - Search a 2D Matrix II
• Leetcode 1351 - Count Negative Numbers in a Sorted Matrix
• Leetcode 239 - Sliding Window Maximum
• Leetcode 209 - Minimum Size Subarray Sum
• LeetCode 230 - Kth Smallest Element in a BST with Code
• advanced-applications-of-binary-search
• Leetcode 96 - Unique Binary Search Trees
• Leetcode 540 - Single Element in a Sorted Array
• Leetcode 1283 - Find the Smallest Divisor Given a Threshold
• Leetcode 74 - Search a 2D Matrix
• Leetcode 340 - Longest Substring with At Most K Distinct Characters
• Leetcode 300 - Longest Increasing Subsequence
• Leetcode 930 - Binary Subarrays With Sum
• Blazingly fast solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Cross-post from r/SoftwareEngineering)
• Leetcode 704 - Binary Search
• Leetcode 643 - Maximum Average Subarray I
• LeetCode - Two Sum Solution with Code
• a-binary-search-template
• Leetcode 33 - Search in Rotated Sorted Array
• Leetcode 1151 - Minimum Swaps to Group All 1’s Together