Number of Substrings Containing All Three Characters
A medium Sliding Window interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Sliding Window
- Sheets
- 1
- Core for
- 5 roles
The problem
Given a string, find the number of substrings that contain all three characters 'a', 'b', and 'c'.
Example 1
- Input
- s = "abcabc"
- Output
- 10
- Why
- There are 10 substrings that contain all three characters.
Example 2
- Input
- s = "aaacb"
- Output
- 3
- Why
- The substrings starting from index 0 or 1 or 2 that reach 'c' and contain 'b' are counted.
Constraints
- 3 <= s.length <= 5 * 10^4
- s consists only of 'a', 'b', and 'c'
How to think about it
Updated 2026-09-09Instead of testing every slice independently, note that any substring ending at the current index is valid as long as its start is at or before the earliest of the latest seen 'a', 'b', and 'c'. All indices from 0 up to min(last_a, last_b, last_c) form valid prefixes in a single arithmetic step.
Approaches, worst first
Test all substring pairs
time O(n^2) · space O(1)
Loop over all start and end points and check if all three characters are present. Too slow for lengths up to fifty thousand.
Track latest occurrence of each characterWrite this one
time O(n) · space O(1)
Keep the most recent index for 'a', 'b', and 'c'. At each position, find the smallest of these three recorded positions. If all three have appeared, exactly min_idx + 1 substrings ending at the current position are valid.
Where people lose marks · 3
- Accumulating the count into a 32-bit signed integer can overflow when the string contains tens of thousands of characters and almost all substrings are valid.
- Adding to the total count before all three characters have been observed at least once.
- Off-by-one error when converting the smallest index to a count; the number of valid starting indices from 0 to min_idx inclusive is min_idx + 1.
The theory behind it
Sliding Window — the ground this problem stands on. All Sliding Window problems
What Sliding Window is
A sliding window is an adjustable magnifying lens placed over a continuous segment of a sequence. Rather than recalculating metrics for every potential subsection from scratch, the window expands rightward by absorbing fresh elements and contracts leftward to expel stale entries. Only data currently framed within the window borders contributes to the active calculation.
When to reach for it
Reach for a sliding window when a question asks for the longest, shortest, or optimal contiguous subarray or substring matching a constraint. Key signals include fixed window sizes like maximum sum across k consecutive values, or dynamic criteria like finding the shortest substring holding all target characters. If the target subset must form an unbroken continuous run, window mechanics replace repetitive segment rescanning.
How the pattern works
Maintain two boundary indices, left and right, defining the active interval alongside a running state accumulator. In each step, expand the right boundary to incorporate the incoming element into state totals. When current state violates the designated problem constraints, increment the left boundary while deducting departing values until validity is restored. Update your tracking metric, whether minimum window length or maximum score, only during valid intervals.
More Sliding Window problems
Target Roles
Core requirement for 5 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .