Number of Substrings Containing All Three Characters

Given a string s consisting only of the characters a, b, and c, return the number of substrings that contain at least one occurrence of each of a, b, and c.

Hints

· Stuck? Reveal one nudge at a time.

Instead of measuring a window, count how many valid substrings end at each index.

A substring ending at i contains all three iff it starts at or before the earliest recent position of a, b, c.

Keep last[a], last[b], last[c] and add min(last) + 1 for each index.

Common doubts

Validity is monotone in the start: once a substring has all three, extending it left keeps them. So valid starts form a prefix, and their count is min(last) + 1.

To include all three characters, the start can't be later than the most recent occurrence of the rarest-to-appear one — i.e. the minimum of the three last indices.

Its last index is -1, so min(last) is -1 and the count contributed is 0 — correct, since no valid substring exists yet.

Interview follow-ups

· What an interviewer asks next.

Expand right; once the window has all three, every start <= left is valid, so add left to the total, shrinking to keep the invariant.

Same idea with an array of K last-seen indices, adding min(last) + 1 per right endpoint.

Fun facts

Counting per right endpoint — 'how many valid windows end here?' — is the second core sliding-window mode, alongside 'how long is the best window?'.
The last-seen-index trick reappears in problems like 'longest substring without repeats' as a way to jump the left pointer.

Asked at

AmazonGoogleMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: s = "abcabc"
Output: 10
There are 10 substrings that contain at least one a, one b, and one c.

Example 2

Input: s = "aaacb"
Output: 3
The valid substrings are "aacb", "acb", and "aaacb".

Constraints

- 3 <= s.length <= 5 * 10^4 - s consists only of characters a, b and c.

This is a counting problem, so fix the right endpoint and count valid left endpoints. The key fact: a substring ending at index i contains all three characters exactly when it starts at or before the earliest of the three most-recent positions of a, b, c. That gives the count for each i in O(1).

Prerequisites

Before you start

· Concepts used directly in the solution.

Count-per-right. Summing, over each right endpoint, the number of valid left starts.

Monotone validity. Once a substring contains all three, extending it further left keeps it valid.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The count

“At least one of each, or exactly one?”

At least one — the substring must contain a, b, and c, in any amounts.

“Are overlapping substrings counted separately?”

Yes — every distinct (start, end) pair that qualifies is counted.

The ideal opening — say it like this

I'll count, for each right endpoint, how many left starts give a valid substring.

A substring ending at i is valid iff it starts at or before the earliest of the last-seen positions of a, b, and c.

So the count for i is min(lastA, lastB, lastC) + 1, and I sum that over all i.

Understand the problem

Worked example — s = "abcabc"

i=2 (c): last=(0,1,2) -> min 0 -> +1   total 1
i=3 (a): last=(3,1,2) -> min 1 -> +2   total 3
i=4 (b): last=(3,4,2) -> min 2 -> +3   total 6
i=5 (c): last=(3,4,5) -> min 3 -> +4   total 10
answer: 10

Key observations

1Aha

Count valid starts per right endpoint

For each right endpoint, the valid start positions form a contiguous prefix 0..min(last), so their number is min(last) + 1 — computable in O(1).

2Aha

The binding constraint is the rarest recent character

A substring covers all three only back to the earliest of the three last-seen positions; that minimum is the furthest-left start that still includes every character.

3Aha

One pass, three integers

You only need the last index of each of a, b, c. No map, no window to shrink — just accumulate min(last) + 1 as you go.

Brute force vs optimal

	Extend from each start	Last-seen count
Idea	From each start, find the first all-three end, add the rest	Per right, add min(last a,b,c) + 1
Time	O(n^2)	O(n)
Space	O(1)	O(1)

The brute finds, for each start, the first valid end and adds the suffix count; the last-seen method flips it to per-right and reads the count off three integers. Full code is in the Approaches selector below.

Summary

Key takeaway

Count per right endpoint: a substring ending at i contains all three characters iff it starts at or before min(last[a], last[b], last[c]), giving min(last) + 1 valid starts. Sum that over all i — one pass, three integers, O(n).

last = [-1, -1, -1]; count = 0
for i, ch in enumerate(s):
    last[ch] = i
    count += 1 + min(last)     # min is -1 until all three are seen
return count