Number of Substrings Containing All Three Characters
WHAT IT SAYS
Given a string of only a, b and c, count the substrings that contain at least one of each.
WHAT IT'S REALLY ASKING
"This is an 'at least' condition, so the usual instinct is upside down: adding characters can never destroy a substring's validity, only create it. Fix a right end — the valid starts can't be scattered, they have to be a solid block reaching back to index 0. So the only question left is where that block stops, and which of the three characters is the one stopping it."
Every substring, check for all three
O(n²) time, O(1) spaceFix a start, extend right, keep three counters, and tick the answer whenever all three are non-zero. Restart from the next index. Correct, obviously — every substring gets inspected.
WHERE THE WORK IS WASTED — You keep re-testing a question whose answer can never flip back. Once s[i..r] contains all three, so does s[i..r+1] and every longer end — yet the inner loop re-checks the three counters at every single one of them, when the honest work ended the moment the third character first appeared. And the outer restart is worse: the scan from i + 1 re-tallies the very characters the scan from i just tallied, only to find the same third character at (usually) the same place.
The scarcest character draws the line; behind it is free.
Presence is upward-closed: a substring containing all three keeps containing all three when you glue more characters onto either end. So for a fixed right end r, the valid starts can't be a scattered set — if start i works, every start to the left of i works too. They form a solid block running from 0 up to some cutoff m, and the entire problem for this r collapses to finding m. m is forced, and here's the argument. Let m = min(last[a], last[b], last[c]), the most recent occurrence of whichever character you've seen least recently. If your start is at or before m, the window contains all three of those last occurrences, so it contains all three characters — valid. If your start is even one step past m, then the character that achieved that minimum has no occurrence at all in [start..r], because its most recent one was at m and it hasn't appeared since — invalid. So m is exactly the cutoff, not an estimate of it, and the number of substrings ending at r is precisely m + 1. Notice which character sets the boundary: not the frequent one, but the one you've gone longest without. It's the bottleneck, and it changes hands as you walk.
Three integers, one pass
O(n) time, O(1) spaceKeep the last index at which you saw each of a, b and c, all starting at −1. At each right end, update the one you just read, then add min(last[a], last[b], last[c]) + 1 to the answer — which is zero, harmlessly, until you've seen all three at least once. No window, no counters, no shrinking.
The same idea wearing a window
O(n) time, O(1) spaceIf you'd rather see it as two pointers: for each right end, shrink the left edge inward as long as the window still contains all three, then add the left edge's index to the answer — because every start before it is valid too. That left edge lands on exactly the m above, so it's the identical count with more moving parts; the last-seen version just reads m straight off instead of walking to it.
Bottleneck Boundary
YOU'LL SEE IT AGAIN WHEN
- The condition is 'contains at least one of each' (or 'covers all of X'), so adding characters can only help — validity is never destroyed by growing.
- For a fixed right end, the valid starts run in an unbroken block back to the start of the array, which means you're counting a boundary index, not enumerating candidates.
- Whether a window qualifies depends on the element you've gone longest without, not on any total or tally.
- The alphabet or required set is small and fixed, so 'when did I last see each required thing' is O(1) to maintain.