Generated by Codex with GPT 5.6 Sol High

Quick facts

The problem in one sentence

Given a string made only of a, b, and c, count every contiguous substring that contains all three characters at least once.

The obvious approach is to inspect every possible substring. A string of length $n$ has $O(n^2)$ substrings, though, and checking each one would make the solution even slower. The constraint of up to 50,000 characters points toward a single pass.

The key observation

Instead of asking whether each possible substring is valid, fix its right endpoint and ask a smaller question:

How many valid substrings end at this position?

While scanning from left to right, remember the most recent index of each required character. Suppose the current right endpoint is right, and the last positions of a, b, and c are $p_a$, $p_b$, and $p_c$.

Let

$$ e = \min(p_a, p_b, p_c). $$

If any character has not appeared, one of those positions is $-1$, so no valid substring can end at right yet.

Otherwise, every starting index from $0$ through $e$ produces a valid substring ending at right. Each such substring includes the latest occurrence of all three characters. A start after $e$ cannot work: it excludes the character whose latest occurrence is at $e$, and by definition that character does not appear again between $e + 1$ and right.

Therefore, the number of valid substrings ending at right is exactly $e + 1$.

For abcabc, the contributions at successive right endpoints are 0, 0, 1, 2, 3, 4. Their sum is 10, which is the answer.

This viewpoint is closely related to a sliding window, but it avoids explicitly moving a left pointer. The three last-seen positions already encode the boundary that matters.

Python solution

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        """Count substrings that contain at least one a, b, and c."""
        last_seen = {"a": -1, "b": -1, "c": -1}
        valid_substring_count = 0

        for right_index, character in enumerate(s):
            # The problem guarantees that every character is a, b, or c.
            last_seen[character] = right_index

            # Any start at or before this position includes the latest
            # occurrence of all three required characters.
            earliest_required_position = min(last_seen.values())
            if earliest_required_position >= 0:
                valid_substring_count += earliest_required_position + 1

        return valid_substring_count

The scan takes $O(n)$ time. Finding the minimum is constant time because the dictionary always contains exactly three entries. The algorithm uses $O(1)$ extra space.

Why the counting does not double-count

Every substring has exactly one right endpoint. At each step, the algorithm counts all and only the valid substrings with that endpoint. Substrings counted at different steps therefore cannot be the same, and summing the per-endpoint counts covers the complete answer.

The method also handles repeated characters naturally. Updating the last-seen position can only move the valid-start boundary to the right, so earlier valid choices are never lost from the total; they have already been counted under their own right endpoints.

Interview follow-ups

Can this be written as a conventional sliding window?

Yes. Keep counts for a, b, and c, expand the right edge, and move the left edge while the window still contains all three. Once removing the old leftmost character makes the window invalid, the new left index equals the number of valid starting positions for the current right endpoint. Add that index to the answer.

Both versions take $O(n)$ time and $O(1)$ space. The last-seen formulation is shorter for exactly three required characters; the count-based window generalizes more directly when the validity rule becomes more complicated.

What if the required character set is not fixed to a, b, and c?

For a small fixed set, store a last-seen position for every required character and use the minimum of those positions. If there are $k$ required characters, recomputing the minimum makes the running time $O(nk)$.

For a large or input-dependent set, use the conventional sliding window with a frequency map and a missing counter. Each character enters and leaves the window at most once, so the total work remains $O(n)$ with $O(k)$ extra space.

What if every required character must appear at least t times?

For the three-character version, keep the most recent t positions of each character in a deque. Once all three deques contain t positions, the earliest among their oldest retained positions determines the same valid-start boundary. This costs $O(n)$ time for the fixed alphabet and $O(t)$ space per character.

A frequency-based sliding window is often simpler for the generalized version: shrink the left edge until removing one more character would violate a required count. The resulting left boundary again tells how many starting positions are valid for the current right endpoint.

How would the solution return the shortest valid substring instead of the count?

Once all three last-seen positions are nonnegative, the latest possible valid start is their minimum. For the current right endpoint, that gives the shortest valid substring ending there. Track the smallest length right_index - earliest_required_position + 1 and its endpoints across the scan.

The running time and extra space stay $O(n)$ and $O(1)$. If ties need a specific policy, such as the leftmost answer, update the saved result only when the new length is strictly smaller.

Can the count be computed from a stream?

Yes. The algorithm never needs earlier string contents, only the current index, three last-seen positions, and the accumulated answer. It can process characters as they arrive and report the running total after each one.

The count can grow quadratically with the input length, even though the algorithm runs in linear time. In a language with fixed-width integers, use a 64-bit type for the total. Python integers grow automatically.

What changes if unrelated characters may also appear?

Nothing fundamental. Update last_seen only when the current character is one of the required characters. Unrelated characters can sit inside a valid substring, but they do not move the boundary established by the most recent a, b, and c.

Takeaway

The useful shift is from enumerating substrings to counting them by right endpoint. Once the latest occurrence of every required character is known, the earliest of those occurrences cleanly divides valid starts from invalid ones. That turns a quadratic search into a compact linear scan.