Number of Substrings Containing All Three Characters | Leetcode 1358 | Optimal Solution using Sliding Window

The problem “Number of Substrings Containing All Three Characters” asks: given a string s consisting only of the characters ‘a’, ‘b’, and ‘c’, count how many substrings contain at least one of each of these three characters. This is a classic substring counting problem that can be solved progressively, starting with a brute force approach, improved with a pruning trick, and finally achieving an O(n) optimal solution using last-seen indices.

Here’s the [Problem Link] to begin with.

Given a string s consisting only of characters a, b and c.

Return the number of substrings containing at least one occurrence of all these characters a, b and c.

Example 1:

Input: s = "abcabc"
Output: 10
Explanation: 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
Explanation: 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

Constraints:

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

Brute Force (Check Every Substring)

Intuition and Approach

• For every start i, expand the end pointer j and keep a set of distinct characters.
• If the set size reaches 3, the current substring [i..j] contains 'a', 'b', and 'c'—increment the count.
• Continue checking for all i and j.

Code

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        count = 0
        n = len(s)
        for i in range(n):
            chars = set()
            for j in range(i, n):
                chars.add(s[j])
                if len(chars) == 3:
                    count += 1
        return count

Why It Works

• The set tracks how many unique characters are in the current substring. When size is 3, the substring qualifies.

Complexity

• Time: O(n^2) (nested loops; set inserts O(1))
• Space: O(1) (set size ≤ 3)

Limitations

• Continues scanning even after finding the first valid j for a given i, missing a large counting shortcut.

Better (Prune With Suffix Count Once Valid)

Intuition and Approach

• Same nested iteration, but employ a smart counting trick:
  • For a fixed i, as soon as the substring [i..j] contains all three chars, then every substring ending at positions j, j+1, ..., n-1 is also valid.
  • So add (n − j) to the answer and break early to move to the next i.

Code

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        count = 0
        n = len(s)
        for i in range(n):
            chars = set()
            for j in range(i, n):
                chars.add(s[j])
                if len(chars) == 3:
                    count += n - j
                    break
        return count

Why It Works

• Once [i..j] is valid, extending the right end keeps the substring valid. Hence count all such extensions in O(1) time.

Complexity

• Time: O(n^2) in worst case, but typically faster due to early breaks
• Space: O(1)

Benefit

• Much faster in practice than pure brute force, especially on strings where the three characters appear frequently.

Optimal (Single Pass Using Last Seen Indices) — O(n)

Core Insight

• Track the latest index where each of 'a', 'b', and 'c' appeared.
• At each position i, if all three have appeared at least once (i.e., all indices are non-negative), then the number of valid substrings ending at i is determined by the leftmost last-seen index among the three.
  • Let last['a'], last['b'], last['c'] be the last indices seen so far.
  • If all are ≥ 0, then the earliest starting point for a valid substring ending at i is min(last.values()).
  • Any start index s in [0..min(last.values())] ensures the substring s..i contains all three chars.
  • So add min(last.values()) + 1 to the total for this i.

This turns the problem into a tight O(n) scan with constant extra space.

Code

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        count = 0
        n = len(s)
        i = 0
        numbers = {"a": -1, "b": -1, "c": -1}
        while i < n:
            numbers[s[i]] = i
            if numbers["a"] >= 0 and numbers["b"] >= 0 and numbers["c"] >= 0:
                count += min(numbers.values()) + 1
            i += 1
        return count

Why It Works

• At index i, the substring must include all three last-seen positions. The start index s must be ≤ the minimum of those last-seen indices so that all three are included. Hence the number of valid starts is min_last + 1.

Complexity

• Time: O(n) – single pass, O(1) work per character
• Space: O(1) – only tracking three indices

Dry Run (Quick)

Consider s = "abcabc":

• i=0 (‘a’): last = {a:0, b:-1, c:-1} → not all present
• i=1 (‘b’): last = {a:0, b:1, c:-1} → not all present
• i=2 (‘c’): last = {a:0, b:1, c:2} → all present → min=0 → add 0+1=1 (substring “abc”)
• i=3 (‘a’): last = {a:3, b:1, c:2} → min=1 → add 2 (substrings starting at 0..1: “abca”, “bca”)
• i=4 (‘b’): last = {a:3, b:4, c:2} → min=2 → add 3 (starts 0..2)
• i=5 (‘c’): last = {a:3, b:4, c:5} → min=3 → add 4 (starts 0..3)

Total = 1 + 2 + 3 + 4 = 10.

Comparison Summary

• Brute Force: Simple to understand; O(n^2) time; no pruning.
• Better: Early break per start index by adding (n − j); still O(n^2) worst-case but faster in practice.
• Optimal: Tracks last seen indices of 'a', 'b', 'c'; counts valid substrings ending at each index in O(1); total O(n) time, O(1) space.

Common Pitfalls and Tips

• Ensure the string contains only ‘a’, ‘b’, ‘c’; the logic relies on exactly three characters.
• In the optimal approach, initialize last-seen to -1 to mark “not seen yet.”
• The counting formula min(last.values()) + 1 is critical: it counts all valid starting indices for substrings ending at i.
• This pattern generalizes: when counting substrings that require a set of required characters, tracking last indices and taking the minimum is often a powerful technique.

Final Takeaway

The optimal solution leverages index tracking to convert a naive O(n^2) enumeration into a slick O(n) scan. By updating the last seen positions of 'a', 'b', and 'c' at each step and summing min_last + 1, it counts all substrings that end at every position and contain all three characters. This approach is both clean and highly efficient – perfect for interviews and production code.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.