Sliding Window — Number of Substrings Containing All Three Characters
↗ LeetCode: Number of Substrings Containing All Three Characters · Medium · pattern chapter →
Given a string s over {a, b, c}, return the number of substrings containing at least one a, one b, and one c.
Example 1 — s = "abcabc" → 10Example 2 — s = "aaacb" → 3Example 3 — s = "abc" → 1
Constraints — 3 ≤ n ≤ 5 · 10⁴. s[i] ∈ {a, b, c}. Brute is O(n²) = 10¹⁰ ops at n=10⁵ (TLE). Sliding window with the "shrink while valid" trick is O(n) = 10⁵ ops.
Interview timer00:00
Approach 1 — Every substring
Intuition. For each [i, j], count occurrences of a, b, c; increment if all ≥ 1.
int numberOfSubstringsBrute(String s) {
int n = s.length(), count = 0;
for (int i = 0; i < n; i++) {
int[] c = new int[3];
for (int j = i; j < n; j++) {
c[s.charAt(j) - 'a']++;
if (c[0] > 0 && c[1] > 0 && c[2] > 0) count++;
}
}
return count;
}Complexity — Time O(n²); Space O(1).
Approach 2 — Sliding window: for each right, count valid lefts
Insight from brute. For each right, find the smallest left such that [left, right] contains all three. Then any left' ∈ [0, left] gives a valid substring ending at right — so we add (left + 1) substrings, no wait we add left when using "smallest left such that INVALID" phrasing.
Cleaner phrasing: extend right; if window has all three, keep shrinking left while still all-three. When the window becomes invalid (some count hits 0), record: number of valid starts for this right is left (indices 0..left-1 all valid).
int numberOfSubstrings(String s) {
int[] cnt = new int[3];
int left = 0, res = 0;
for (int right = 0; right < s.length(); right++) {
cnt[s.charAt(right) - 'a']++;
while (cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0) {
cnt[s.charAt(left) - 'a']--;
left++;
}
res += left; // valid starts are 0..left-1
}
return res;
}Complexity — Time O(n); Space O(1).
Approach 3 — Track last-seen positions of each char (O(1) map)
Insight from sliding. For each right, the smallest left giving all-three is min(lastA, lastB, lastC) + 1. So valid starts = min(lastA, lastB, lastC) + 1 if all three have been seen.
int numberOfSubstringsLast(String s) {
int[] last = {-1, -1, -1};
int res = 0;
for (int i = 0; i < s.length(); i++) {
last[s.charAt(i) - 'a'] = i;
res += Math.min(last[0], Math.min(last[1], last[2])) + 1;
}
return res;
}Complexity — Time O(n); Space O(1). One-pass, no inner while — slightly cleaner.
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Every substring | O(n²) | O(1) | baseline |
| Sliding window | O(n) | O(1) | expected optimum |
| Last-seen tracking | O(n) | O(1) | polish — cleanest single pass |
When to use which
- First pass — sliding window is the pattern-recognition answer.
- Interviewer asks "simpler code?" → last-seen version.
- Generalize to k distinct required chars → last-seen extends to
min(lastX) + 1. - "Contains at least K of each char" → this becomes a
need[]/have[]problem — see Minimum Window Substring.
Related problems
- Minimum Window Substring — need/have generalization
- Longest Substring with At Most K Distinct Characters
- Subarrays with K Different Integers