Number of Substrings Containing All Three Characters: Sliding Window

LeetCode 1358 Number of Substrings Containing All Three Characters asks you to count the number of substrings of a string s that contain at least one occurrence of each character 'a', 'b', and 'c'.

For example, given s = "abcabc", there are 10 valid substrings. A brute-force approach would check every possible substring, but that runs in O(n^2) time. You can do this in a single pass with a sliding window.

The approach: track last occurrences

The cleanest way to solve this problem is to track the last index where you saw each of the three characters. As you scan through the string from left to right, at each position i, every substring that starts at or before the earliest of the three last positions and ends at i will be valid. That count is 1 + min(last_a, last_b, last_c).

Why does this work? If the most recent 'a' was at index 2, the most recent 'b' at index 3, and the most recent 'c' at index 5, then any substring ending at index 5 that starts at index 0, 1, or 2 will contain all three characters. That is 1 + min(2, 3, 5) = 3 substrings. Any substring starting after index 2 would miss the 'a'.

def number_of_substrings(s: str) -> int:
    last = {c: -1 for c in "abc"}
    count = 0

    for i, c in enumerate(s):
        last[c] = i
        count += 1 + min(last.values())

    return count

This runs in O(n) time and O(1) space. There are only three keys in the dictionary, so min(last.values()) is a constant-time operation.

The sliding window approach

You can also solve this with a classic sliding window that uses frequency counting. Maintain a window with left and right pointers. Expand right to add characters. Whenever the window contains all three characters, every extension of that window to the right is also valid. So you add len(s) - right to the count, then shrink from the left.

def number_of_substrings(s: str) -> int:
    freq = {c: 0 for c in "abc"}
    left = 0
    count = 0

    for right in range(len(s)):
        freq[s[right]] += 1
        while all(freq[c] > 0 for c in "abc"):
            count += len(s) - right
            freq[s[left]] -= 1
            left += 1

    return count

Both approaches are correct and run in O(n) time. The sliding window version is more general and follows the standard template you see in other problems. The last-occurrence version is more concise for this specific problem.

Why the counting math works

The key insight in the sliding window version is the line count += len(s) - right. When you find a valid window ending at right, you know that every longer substring ending at the same or later positions is also valid. There are len(s) - right such substrings (the current one plus every extension to the right).

In the last-occurrence version, the math is different but equivalent. min(last.values()) gives you the position of the "bottleneck" character, the one you saw least recently. Any starting position from 0 up to that index gives a valid substring ending at the current position. That is min(last.values()) + 1 starting positions, which equals 1 + min(last.values()) when the dictionary is initialized to -1.

Walking through the algorithm

Let's trace the sliding window approach on s = "abcabc". At each step, we expand right, check if the window is valid (contains all three characters), and if so, count len(s) - right substrings and shrink from the left.

After processing the entire string, the total count is 10. You can verify: the valid substrings are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc", and "abc" (the one starting at index 3).

Complexity analysis

Both approaches use constant space because the frequency map or last-occurrence map always has exactly three keys. Time is O(n) because each character is visited at most twice (once by right, once by left in the sliding window version, or just once in the last-occurrence version).

The building blocks

This problem decomposes into two reusable pieces that you will see in many other sliding window problems.

1. Window validity check

The core question at each step is: does the current window contain all required characters? Here, "required" means at least one of each 'a', 'b', and 'c'. The same pattern shows up in Minimum Window Substring, Find All Anagrams, and Permutation in String. The data structure changes (counter, dict, array), but the question is always the same.

all(freq[c] > 0 for c in "abc")

2. Counting valid extensions

Once you find a valid window, you need to count how many substrings it produces. In "find the minimum" problems, you record the window length and keep shrinking. In counting problems like this one, you count all possible extensions and then shrink.

count += len(s) - right

These two building blocks snap together to solve any "count substrings with property X" problem. The property check changes, but the counting mechanism stays the same.

Edge cases

Before submitting, make sure your solution handles these inputs:

• Only two distinct characters like "aabb": no valid substrings because 'c' never appears. Both solutions correctly return 0 (the last-occurrence approach keeps last['c'] = -1, so min(last.values()) is always -1, contributing 1 + (-1) = 0 at each step).
• Minimum valid string "abc": exactly 1 valid substring. The window becomes valid only at the last character.
• All same characters like "aaaa": returns 0. Two of the three required characters are missing entirely.
• Long strings: both solutions run in O(n) with O(1) space, so strings up to 50,000 characters (the problem's constraint) are handled efficiently.

From understanding to recall

Reading this walkthrough gives you the intuition, but solving this problem from scratch in an interview requires recall. Spaced repetition bridges the gap. You revisit the window-validity-check and counting-extensions building blocks at increasing intervals, writing the code each time, until the pattern is automatic.

The next time you see a "count substrings containing..." problem, you will recognize the shape immediately and know exactly which building blocks to assemble.

Related posts

• Longest Substring Without Repeating Characters - The classic sliding window problem on strings, using a set instead of a frequency map
• Minimum Window Substring - A harder version where you need to find the smallest window containing all required characters
• Find All Anagrams in a String - Another sliding window plus frequency counting problem with a fixed-size target

Solving this problem is the first step. Retaining it so you can reproduce the solution weeks later is what matters for interviews. CodeBricks uses spaced repetition to drill the building blocks behind sliding window problems so that you internalize the pattern, not just memorize individual solutions.