Number of Substrings Containing All Three Characters
Medium · Sliding Window · Hash Table · String · Sliding Window
Problem
You are given a string s made only of the characters 'a', 'b' and 'c'.
Return the number of substrings that contain at least one 'a', at least one 'b' and at least one 'c'. Substrings at different positions count separately, even when their text is the same.
Examples
Input: s = "abcab" Output: 6
The qualifying substrings are "abc", "abca", "abcab", "bca", "bcab" and "cab".
Input: s = "aabb" Output: 0
There is no c anywhere, so nothing qualifies.
Input: s = "aaacb" Output: 3
A substring must reach the b at the end and include an a, so it ends at the last index and starts at one of the three a.
Constraints
- 3 <= len(s) <= 5 · 10^4
- s contains only a, b and c
Approaches
- Extend from every start — time O(n²), space O(1)
Follow-up
What if the required letters were any set of k letters? Keep the last position of each and use the minimum (the first use case). What if the rule were "some letter at least k times"? The window still only becomes valid as it grows, so the same count-the-extensions trick works (the second use case).
Related problems
Start free on Cariara · Coding problems · System design studio
