Number of Substrings Containing All Three Characters
Number of Substrings Containing All Three Characters: given a string of only a, b, and c, count the substrings that contain at least one of each.
- 3 <= s.length <= 5 x 10⁴
- s only consists of 'a', 'b' or 'c' characters.
Intuition
Number of substrings containing all three characters counts substrings of a string over a, b, and c that contain at least one of each.
Checking every substring is O(n²). The efficient approach turns on a monotonicity observation:
- If a substring from left to right contains all three characters, then extending it further right still contains all three — so once a valid window is found, every longer one is valid too.
That means for each right endpoint, the valid left endpoints form a contiguous range starting at 0. Finding the rightmost valid left position immediately gives the count.
The cleanest formulation tracks the last seen index of each character. For a given right endpoint, the smallest of those three indices is the latest position where all three are still present. Every left endpoint from 0 up to that index yields a valid substring, so the count contributed is min(lastA, lastB, lastC) + 1.
The + 1 accounts for left endpoint 0 being valid, and omitting it undercounts by exactly one per position.
Initialising all three last-seen indices to −1 handles the prefix where some character has not yet appeared — the minimum is then −1 and the contribution is 0, which is correct.
The sliding-window alternative shrinks from the left while the window remains valid, then adds left + 1. Equivalent, and some find the window framing more familiar than the last-seen indices.
One pass with three variables gives O(n) time and O(1) space.
For each right endpoint, count the valid left endpoints directly. Tracking the last seen index of each of a, b, c means min(last) + 1 is exactly how many starting positions produce a substring containing all three — no window shrinking needed.
Approach
Before reading on: price up what counting everything costs here, then ask what makes a window invalid, and which pointer should move when it is. Aim for O(n) time and O(1) space.
Spot the monotonicity
A valid substring stays valid when extended right, so for each right endpoint the valid left endpoints form a contiguous range from 0.
Track last-seen indices
Record the most recent position of each of the three characters. The smallest of them is the latest left endpoint that still includes all three.
Initialise to -1
Before a character has appeared, its index is -1, making the minimum -1 and the contribution 0 — correct for the prefix with no valid substrings.
Add the count per position
Contribute min(lastA, lastB, lastC) + 1 at each right endpoint. The + 1 counts left endpoint 0 and omitting it undercounts by one per position.
Update after counting
Record the current character's index, then move on. Each position is handled in constant time with no inner loop.
Know the window alternative
Shrink from the left while the window stays valid, then add left + 1. Equivalent, and the window framing is more familiar to some.
Cost of the approach
One pass with three variables gives O(n) time and O(1) space, replacing the O(n²) enumeration.
Solution & live demo
Common pitfalls
Adding 1 per valid window
if min(last) >= 0: total += 1
total += min(last) + 1
Every start from 0 through min(last) yields a valid substring ending here — that's min(last) + 1 of them, not one. Counting singly undercounts massively.
Forgetting the -1 initialisation does the guarding
last = [0, 0, 0]
last = [-1, -1, -1]
Seeding with 0 claims each character was seen at index 0, so counting begins before all three have appeared. Starting at −1 makes min(last) + 1 evaluate to 0 until every character has been seen at least once.
Using a shrinking window
while have all three: shrink and count
last[ord(ch) - ord('a')] = i
total += min(last) + 1The window approach works but needs a frequency map and a shrink loop. Three last-seen indices carry the same information in constant space with no inner loop at all.
Edge cases
Some last value stays -1 throughout, so the sum is 0.
Same — the answer is 0.
Only the last position contributes, adding 0 + 1 = 1.
Handled naturally — min(last) stops advancing, so each position adds the same count.