Number of Substrings Containing All Three Characters

Count by right end, using each letter's last position

time O(n)space O(1)

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.

Details

Animated on: s = "aabcabc" — how many substrings contain at least one 'a', one 'b' and one 'c'?

Problem:Number of Substrings Containing All Three CharactersMedium

Count by right end, using each letter's last position

step 1 / 9

[0]

[1]

[2]

[3]

[4]

[5]

[6]

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.

Pseudocode

1FUNCTION countSubstrings(s):
2  last[a] <- -1
3  last[b] <- -1
4  last[c] <- -1
5  total <- 0
6  FOR r <- 0 TO LENGTH(s) - 1:
7    last[s[r]] <- r
8    k <- MIN(last[a], last[b], last[c])
9    IF k >= 0:
10      total <- total + k + 1
11  RETURN total

← / → step · space play · Home restart

Every step in words

Show all 9 steps

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.
s[0]='a' extends the prefix, but 'b' and 'c' still have not appeared anywhere in "a", so no substring ending at index 0 can contain all three. total stays 0.
s[1]='a' extends the prefix, but 'b' and 'c' still have not appeared anywhere in "aa", so no substring ending at index 1 can contain all three. total stays 0.
s[2]='b' extends the prefix, but 'c' still has not appeared anywhere in "aab", so no substring ending at index 2 can contain all three. total stays 0.
s[3]='c' moves that letter's latest copy to index 3. Of the three letters, 'a' is the one whose latest copy is furthest back, at index 1 — so a substring ending at 3 still reaches all three exactly when it starts at or before 1. That is 2 valid starts (indices 0 through 1, green), lifting total from 0 to 2.
s[4]='a' moves that letter's latest copy to index 4. Of the three letters, 'b' is the one whose latest copy is furthest back, at index 2 — so a substring ending at 4 still reaches all three exactly when it starts at or before 2. That is 3 valid starts (indices 0 through 2, green), lifting total from 2 to 5.
s[5]='b' moves that letter's latest copy to index 5. Of the three letters, 'c' is the one whose latest copy is furthest back, at index 3 — so a substring ending at 5 still reaches all three exactly when it starts at or before 3. That is 4 valid starts (indices 0 through 3, green), lifting total from 5 to 9.
s[6]='c' moves that letter's latest copy to index 6. Of the three letters, 'a' is the one whose latest copy is furthest back, at index 4 — so a substring ending at 6 still reaches all three exactly when it starts at or before 4. That is 5 valid starts (indices 0 through 4, green), lifting total from 9 to 14.
Each of the 7 right ends contributed 0 + 0 + 0 + 2 + 3 + 4 + 5, so "aabcabc" holds 14 substrings containing all three letters — counted in one pass, never by listing them.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Number of Substrings Containing All Three Characters in the editor All Sliding Window problems Back to roadmap