#1358

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Number of Substrings Containing All Three Characters

Count all substrings containing at least one of each character a, b, and c using a sliding window approach efficiently.

Problem Statement

Given a string s consisting only of the characters 'a', 'b', and 'c', determine how many substrings contain at least one occurrence of all three characters. Each substring should be counted independently, and overlapping substrings are valid.

For example, with s = "abcabc", substrings like "abc", "bca", and "cab" each contain all three characters. Your task is to return the total count of such substrings. The input length is constrained to be between 3 and 50,000, and the string only contains 'a', 'b', and 'c'.

Examples

Example 1

Input: s = "abcabc"

Output: 10

The substrings containing at least one occurrence of the characters a, b and c are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (again).

Example 2

Input: s = "aaacb"

Output: 3

The substrings containing at least one occurrence of the characters a, b and c are "aaacb", "aacb" and "acb".

Example 3

Input: s = "abc"

Output: 1

Example details omitted.

Constraints

3 <= s.length <= 5 x 10^4
s only consists of a, b or c characters.

Solution Approach

Sliding Window with Last Seen Indices

Maintain the last seen index for 'a', 'b', and 'c'. As you iterate through the string, calculate the minimum of these indices to determine how many substrings ending at the current character contain all three characters. Increment a running total using this minimum index.

Hash Table for Character Tracking

Use a small hash table or fixed-size array to store the latest positions of 'a', 'b', and 'c'. This allows constant-time updates and ensures that checking for presence of all characters does not require scanning the entire substring, which avoids O(n^2) complexity.

Optimized Count Accumulation

At each step, the number of new valid substrings is equal to the minimum last seen index plus one. Accumulate this count iteratively to get the final answer. This technique leverages the running state to efficiently count without enumerating substrings explicitly.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because we scan the string once, updating last seen indices and computing the minimum each iteration. Space complexity is O(1) since we only store the latest positions of three characters, independent of string length.

What Interviewers Usually Probe

Candidate identifies sliding window as the optimal approach instead of brute force substring checking.
Candidate demonstrates correct running state updates for each character and uses minimum index for counting.
Candidate maintains O(1) extra space and explains why checking all substrings is unnecessary.

Common Pitfalls or Variants

Common pitfalls

Attempting to check every possible substring, resulting in O(n^2) time.
Failing to update last seen indices correctly when characters repeat.
Counting substrings incorrectly by not considering the minimum last seen position of all three characters.

Follow-up variants

Count substrings containing at least K distinct characters instead of exactly three specific ones.
Extend the problem to larger alphabets beyond 'a', 'b', 'c', requiring dynamic hash table updates.
Compute the longest substring containing all three characters rather than the total number of substrings.

FAQ

What is the most efficient approach for Number of Substrings Containing All Three Characters?

Use a sliding window with last seen indices for 'a', 'b', and 'c', updating running totals to count substrings in O(n) time.

Can this problem be solved using brute force?

Technically yes, but enumerating all substrings is O(n^2) and will exceed time limits for long strings.

Why is a hash table helpful in this problem?

It allows constant-time tracking of the latest positions of each character, which is essential for efficient substring counting.

How does the minimum last seen index determine substring count?

The minimum last seen index indicates how many starting positions create valid substrings ending at the current character, giving an O(n) accumulation method.

Does this pattern generalize to more characters?

Yes, the sliding window with running state updates can handle any fixed-size set of characters efficiently with similar logic.

terminal

Solution

Solution 1: Single Pass

We use an array $d$ of length $3$ to record the most recent occurrence of the three characters, initially all set to $-1$.

1

2

3

4

5

6

7

8

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        d = {"a": -1, "b": -1, "c": -1}
        ans = 0
        for i, c in enumerate(s):
            d[c] = i
            ans += min(d["a"], d["b"], d["c"]) + 1
        return ans

Continue Practicing

#1297 maximum number of occurrences of a substring #1156 swap for longest repeated character substring #1016 binary string with substrings representing 1 to n