165. All Three Present
A signal receiver logs a stream of symbols, each one being a, b or c, and the stream is stored as the string s. An engineer is interested in every stretch of the stream that shows all three symbols at least once, because only those stretches carry a complete message.
Return the number of substrings of s that contain at least one a, at least one b and at least one c. Substrings are counted by their position, so two equal substrings that start at different indices are counted separately. The result fits in a 32-bit integer for every allowed input.
Example 1
- Input:
- s = "abcab"
- Output:
- 6
- Explanation:
The substrings that hold all three letters are "abc", "abca", "abcab", "bca", "bcab" and "cab", so the answer is 6.
Example 2
- Input:
- s = "aabbcc"
- Output:
- 4
- Explanation:
Only substrings that reach from an a to a c can contain all three. A valid substring must start at index 0 or 1 (an a) and end at index 4 or 5 (a c), which gives 2 x 2 = 4 substrings.
Example 3
- Input:
- s = "ccc"
- Output:
- 0
- Explanation:
The letters a and b never appear, so no substring qualifies and the answer is 0.
Constraints
1 ≤ s.length ≤ 60000
s consists only of the characters 'a', 'b' and 'c'
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)