Number of Substrings Containing All Three Characters

Number of Substrings Containing All Three Characters

What is this problem about?

The Number of Substrings Containing All Three Characters problem asks you to count substrings that contain at least one 'a', one 'b', and one 'c'. Instead of checking each substring, the efficient approach uses the "last occurrence" technique or a variable sliding window that counts from the right. This coding problem is a clean variable-window string problem.

Why is this asked in interviews?

Microsoft, Meta, Amazon, TikTok, Google, and Bloomberg ask this because it tests the ability to count "at least one of each" substrings efficiently. The standard approach of extending until all three are covered, then counting how many right-extensions remain valid, is the key insight. The hash table, sliding window, and string interview pattern is the core.

Algorithmic pattern used

Last occurrence tracking. For each right endpoint r, track the last seen position of 'a', 'b', 'c'. The minimum of these three positions (call it minPos) means every substring starting from index 0 to minPos and ending at r contains all three characters. Add (minPos + 1) to the count for each r.

Example explanation

s = "abcabc". Track last_a, last_b, last_c (initialized to -1).

• r=0 ('a'): last_a=0. min(-1,-1,...) = -1. Add 0.
• r=1 ('b'): last_b=1. min(0,-1,-1) = -1. Add 0.
• r=2 ('c'): last_c=2. min(0,1,2) = 0. Add 1. (Substring [0..2]).
• r=3 ('a'): last_a=3. min(3,1,2) = 1. Add 2. (Substrings [0..3],[1..3]).
• r=4 ('b'): last_b=4. min(3,4,2) = 2. Add 3.
• r=5 ('c'): last_c=5. min(3,4,5) = 3. Add 4. Total = 0+0+1+2+3+4 = 10.

Common mistakes candidates make

• Sliding window that only expands right without leveraging the "last occurrence" shortcut.
• Computing minPos + 1 as the number of valid start positions — this is correct but often confused.
• Not initializing last positions to -1 (meaning "not yet seen").
• Off-by-one: when minPos = -1, it means all three haven't appeared yet → 0 subarrays.

Interview preparation tip

"Count substrings containing all k characters" problems use the last-occurrence trick: once you've seen all required characters, the earliest last-occurrence position determines how many starting positions give valid substrings. Adding (minPos + 1) per right endpoint is the elegant O(n) solution. Practice extending this to "all k distinct characters" and "at least one of each of m characters" — the same technique applies.