Number of Substrings Containing All Three Characters — Last-Seen Index Trick (LC 1358)

Problem Statement#

LeetCode 1358 — Number of Substrings Containing All Three Characters (Medium)

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

Constraints:

• 3 <= s.length <= 5 * 10^4
• s consists only of 'a', 'b', 'c'

Input:  s = "abcabc"
Output: 10

Input:  s = "aaacb"
Output: 3

Why This Problem Matters#

This problem showcases a powerful counting technique: instead of counting valid substrings directly, count how many valid substrings end at each position. This transforms O(n^2) enumeration into an O(n) pass.

The last-seen index trick eliminates the need for explicit window management or frequency maps. It appears in interviews at Google, Amazon, and Meta as a test of whether candidates can reason about the structure of valid substrings rather than brute-forcing enumeration. The broader pattern — "at each right boundary, count how many left boundaries give a valid substring" — generalizes to a wide class of substring counting problems.

The Core Insight#

For each position i, track:

• last['a'] = most recent index where 'a' appeared (or -1 if unseen)
• last['b'] = most recent index where 'b' appeared (or -1 if unseen)
• last['c'] = most recent index where 'c' appeared (or -1 if unseen)

A substring s[left..i] contains all three characters if and only if left <= min(last['a'], last['b'], last['c']).

So the number of valid substrings ending at i = min(last['a'], last['b'], last['c']) + 1.

Why +1? Left boundary can be any index from 0 to min_last inclusive — that is min_last + 1 valid left boundaries. If any character is unseen, min_last = -1 and the count is 0.

Visual Dry Run#

Input: s = "abcabc"

Answer: 10

Solution (Optimal)#

def numberOfSubstrings(s: str) -> int:
    last = {'a': -1, 'b': -1, 'c': -1}
    ans = 0
 
    for i, c in enumerate(s):
        last[c] = i
        ans += min(last.values()) + 1
 
    return ans

var numberOfSubstrings = function(s) {
    const last = { 'a': -1, 'b': -1, 'c': -1 };
    let ans = 0;
 
    for (let i = 0; i < s.length; i++) {
        last[s[i]] = i;
        const minLast = Math.min(last['a'], last['b'], last['c']);
        ans += minLast + 1;
    }
 
    return ans;
};

Time: O(n) — single pass; min over 3 values is O(1) Space: O(1) — fixed-size array of 3 last-seen indices

Common Mistakes#

• Brute force O(n^2) enumeration — generating all O(n^2) substrings and checking each is TLE for n = 5 * 10^4
• Using a frequency count instead of last-seen index — frequency requires explicit window management; last-seen is O(1) per step
• Initialising last to 0 instead of -1 — 0 falsely indicates character at index 0 has been seen; use -1 as sentinel
• Thinking min_last + 1 counts characters — it counts valid left boundary positions (indices 0 through min_last)
• Applying this trick when condition is "exactly one of each" — the trick works only for "at least one of each"

Interview Tips#

• State the core insight upfront: "For each right boundary i, valid substrings ending here = min(last_seen) + 1"
• No left pointer is needed — last-seen indices implicitly encode the earliest valid left boundary
• The single expression min(last.values()) + 1 replaces an entire inner loop
• This is not a traditional sliding window — it is a direct count, no shrinking needed

Follow-up Questions#

• Larger alphabet: generalize last to all required characters; formula min(last.values()) + 1 still applies
• At least k occurrences of each: last-seen trick no longer applies; use sliding window with frequency map
• Exactly one of each: use atLeast(1) - atLeast(0) with the formula applied twice
• Count in reverse (for each left, how many right?): binary-search for smallest valid right for each left — O(n log n)

Key Takeaways#

• Track only the last-seen index of each required character — no frequency map, no explicit window
• Valid substrings ending at i = min(last['a'], last['b'], last['c']) + 1
• Initialise last-seen to -1; the formula returns 0 automatically when any character is unseen
• Single pass, O(1) arithmetic per step — no inner loop, no shrink logic, no left pointer
• Time O(n), space O(1) — the canonical solution for "count substrings containing at least one of each required character"