# 1358 Number of Substrings Containing All Three Characters

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 104`
• `s` only consists of a, b or c characters.
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 `````` ``````class Solution: def numberOfSubstrings(self, s: str) -> int: res = i = 0 count = {c: 0 for c in 'abc'} for j in range(len(s)): count[s[j]] += 1 while all(count.values()): count[s[i]] -= 1 i += 1 res += i return res ''' `last` will record the position of last occurrence. If the ending index of substring is `i`, the starting position should be on the left of min(last), in order to have all 3 different letters. And in this case, the starting index can be in range [0, min(last)], min(last) + 1 in total. ''' class Solution: def numberOfSubstrings(self, s: str) -> int: res, last = 0, [-1] * 3 for i, c in enumerate(s): last[ord(c) - 97] = i res += 1 + min(last) return res``````