Number of Substrings Containing All Three Characters
Count the substrings of a string of a, b and c that contain at least one of each letter, with a sliding window that counts all right-hand extensions at once.
Problem Understanding
Number of Substrings Containing All Three Characters: given a string s of the letters a, b and c, return how many substrings contain at least one occurrence of each.
Examples: "abcabc" → 10; "aaacb" → 3; "abc" → 1.
The Intuition: A Valid Window Stays Valid to the Right
Containing all three letters is monotone: a longer string that includes a valid one is valid too. So instead of checking every substring:
- Grow the sliding window until it holds a, b and c.
- Count every substring starting at
leftthat ends atrightor later:n − rightof them. - Shrink from the left and repeat while still valid.
The window with letter counts is the same as in Minimum Window Substring, and counting many substrings per step echoes Count Number of Nice Subarrays.
Interactive Walkthrough
AMBER = MORE END POINTS, EACH ONE MORE SUBSTRING
EMPTY WINDOW
0
1
2
3
4
5
a
:
b
:
c
:
total
0
Count substrings of "abcabc" with at least one a, b and c
Next
Add s[0] = 'a': a 1, b 0, c 0
s
On each count step the window with all three letters is filled and the cells after it are marked: each marked cell is one more end point. Try Early to see one step count three substrings.
Dry Run Table
Input: "abcabc", n = 6.
| Window | Added (n − right) | Total |
|---|---|---|
| s[0..2] = abc | 6 − 2 = 4 | 4 |
| s[1..3] = bca | 6 − 3 = 3 | 7 |
| s[2..4] = cab | 6 − 4 = 2 | 9 |
| s[3..5] = abc | 6 − 5 = 1 | 10 |
Answer: 10.
The Solution Template
Three counters and a shrinking window.
Number of Substrings Containing All Three Characters Code
1var numberOfSubstrings = function(s) {2 const count = [0, 0, 0];3 let left = 0, total = 0;4 const n = s.length;5 for (let right = 0; right < n; right++) {6 count[s.charCodeAt(right) - 97]++;7 while (count[0] && count[1] && count[2]) {8 total += n - right;9 count[s.charCodeAt(left++) - 97]--;10 }11 }12 return total;13};
Edge Cases & Common Mistakes
- Adding 1 instead of n − right: counts only the shortest valid substring per start.
- A letter missing entirely: the window never becomes valid; the answer is 0.
- Overflow: with n up to 5 × 10⁴ the total stays below 2³¹, but use 64-bit if you generalize.
- Using
ifinstead ofwhile: misses starts that are still valid after one shrink. - Brute force: O(n²) substrings is too slow for n = 5 × 10⁴.
Summary
Grow the window; while it contains a, b and c, add n − right and shrink from the left. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet