1358. Number of Substrings Containing All Three Characters

Difficulty: Medium | Date: 2026-06-30

Patterns: Sliding Window Data Structures: String

Problem

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

My Approach

I recognized it as sliding window but got stuck on two things: when to shrink, and how to count. My instinct was to expand until valid and count then, but I couldn’t figure out the math.

The counterintuitive move: shrink while the window IS valid (not when it’s invalid like most sliding window problems). Keep shrinking left until the window breaks. At that point, left tells you how many valid starting positions exist for the current right endpoint.

Key Insight

The result += left counting formula for “at least” substring problems.

After shrinking left until the window just becomes invalid:

The window [left, right] is the first invalid window
So [left-1, right], [left-2, right], …, [0, right] are all valid
That’s exactly left valid substrings ending at right
Add left to result for every right

This works because once a window ending at right is valid, making it longer (moving start left) keeps it valid. So you only need to find the boundary.

Solution

def numberOfSubstrings(s: str) -> int:
    count = {'a': 0, 'b': 0, 'c': 0}
    left = 0
    result = 0
 
    for right in range(len(s)):
        count[s[right]] += 1
 
        # shrink while valid — opposite of typical sliding window
        while count['a'] > 0 and count['b'] > 0 and count['c'] > 0:
            count[s[left]] -= 1
            left += 1
 
        # left = number of valid starting positions for this right
        result += left
 
    return result

Complexity

Time: O(n) - each character is added and removed from the window at most once
Space: O(1) - fixed-size count dict (only 3 keys)

The Reusable Formula

For “count substrings with at least X” problems:

Shrink while valid, stop when invalid
result += left at each step

Contrast with “count substrings with exactly X” = atLeast(X) - atLeast(X+1)

Napman's Notes

Explorer

Number of Substrings Containing All Three Characters