Number of Substrings Containing All Three Characters
MediumStringSliding Window·GoogleAmazon
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
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" (start at index 3).
Example 2:
Input:s = "aaacb"
Output:3
The substrings containing at least one occurrence of the characters a, b and c are "aaacb", "aacb" and "acb".
Constraints:
3 ≤ s.length ≤ 5 × 10⁴
s only consists of characters a, b or c.
Hints
Hint 1How can we solve this with a nested loop?▼
For each starting index i, keep adding characters to a set until we have 'a', 'b', and 'c'. If we find all three at index j, then all substrings ending at j, j+1, ..., n-1 starting at i are valid. There are exactly n - j such substrings. We can add this count and break early.
Hint 2Can we optimize this to O(n) using tracking?▼
Keep track of the last seen position of each character: 'a', 'b', and 'c'. For each right pointer, the shortest valid substring ending at right must start at the minimum index among these three last seen positions.
Hint 3How do we calculate valid substrings ending at right?▼
If min_idx = min(last_seen['a'], last_seen['b'], last_seen['c']) is ≥ 0, then any starting index from 0 to min_idx forms a valid substring. Thus, there are exactly min_idx + 1 valid substrings.
🌐 Real-World Analogy
Multi-Component Assembly Line
Imagine a conveyor belt supplying parts. To build a product, you need exactly one of each component: A, B, and C. As the belt moves forward, once you have received at least one of each part, any suffix of parts ending with the current one forms a valid set. Knowing the last seen positions of each component helps you quickly find the minimal window of parts needed to assemble a product, and lets you count how many potential batches of parts contain all required pieces.
Interactive Visualizer
🚀
Optimal Search (Last Seen Positions)
Time O(n)Space O(1)
We run a single pass, updating the last-seen position of each character. For any current ending index right, the shortest valid window must start at min_idx = min(last_seen['a'], last_seen['b'], last_seen['c']). If min_idx ≥ 0, there are exactly min_idx + 1 valid starting positions, which we add directly to our count.
Discussion
…