# 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`

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`.

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
``````

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.