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.
Open on LeetCode ↗Intuition
The trap is reaching for a sliding window or, worse, enumerating every substring and checking each one for all three characters, which is O(n^2) before you even count. Instead fix the right end and ask how many valid substrings end there. If the last occurrences of a, b, and c are at positions la, lb, lc, then any start index at or before min(la, lb, lc) gives a substring containing all three. That is min(la, lb, lc) + 1 substrings, added at every position — a counting trick that needs three integers and no window at all.
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
Count by right endpoint
Enumerating all substrings is O(n^2) even before checking each one. Instead, for each right endpoint count how many left endpoints work. Summing those counts covers every substring exactly once, since each substring has exactly one right endpoint.
Track the last seen index of each character
Keep last = [-1, -1, -1] for a, b, and c, updating last[ord(ch) - ord('a')] = i at each step. A substring s[j..i] contains all three exactly when j is at or before every one of those three positions — that is, j <= min(last).
Add min(last) + 1 each step
The valid starts are 0, 1, ..., min(last), so there are min(last) + 1 of them. If any character has not appeared yet, min(last) is -1 and the term is 0, which handles the prefix correctly with no special case. Sum across all i for the answer. One pass, O(n) time, O(1) space.
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.