Pattern visualizer
Number of Substrings Containing All Three Characters
A substring qualifies as soon as it has seen all three letters, and adding more letters on the left can never take that away. So fix the right end at index r and ask how far left a start may sit: the substring reaches all three exactly when it stretches back past the last occurrence of every letter. The binding one is whichever letter's most recent copy is furthest back, at index k — every start from 0 through k works and every start after k misses that letter, giving k + 1 substrings for this right end. Keeping only the last seen index of each of the three letters makes that a single scan with three counters, no window to shrink and nothing to re-scan. Animated on: s = "aabcabc" — how many substrings contain at least one 'a', one 'b' and one 'c'?.
Count by right end, using each letter's last position
Counting every substring of "aabcabc" that holds at least one 'a', one 'b' and one 'c'. Testing all 28 substrings one by one re-reads the same letters over and over, so instead each step fixes the RIGHT end and asks only how many left ends still work.
1FUNCTION countSubstrings(s):2 last[a] <- -13 last[b] <- -14 last[c] <- -15 total <- 06 FOR r <- 0 TO LENGTH(s) - 1:7 last[s[r]] <- r8 k <- MIN(last[a], last[b], last[c])9 IF k >= 0:10 total <- total + k + 111 RETURN total
← / → step · space play · Home restart