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.
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
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.