Number of Substrings Containing All Three Characters

This chapter covers the optimal resolution for finding the total number of substrings that contain at least one occurrence of every required character (a, b, and c) within a given string. We will progress from a naive brute-force approach to an optimized single-pass linear time algorithm using last-seen character tracking.

1. Problem Statement and Definition

You are given a string consisting only of the characters a, b, and c. Your objective is to compute the total number of valid substrings that contain all three characters (a, b, and c) at least once.

• Substring Definition: Any contiguous sequence of characters within a string.
• Validity Condition: A substring is valid if its character frequency set includes $\ge 1$ count of 'a', $\ge 1$ count of 'b', and $\ge 1$ count of 'c'.

Real-Life Analogy: Scanning a Document for Keyword Windows

Imagine reading a long scroll of text containing only three types of stamps: A, B, and C. You want to count how many distinct ending positions culminate in a window that possesses all three stamps. Instead of cutting out every possible starting and ending point from scratch (which is redundant), you walk across the string, remember the last seen index of each stamp, and instantly calculate how many valid left-expansions exist up to that moment.

2. Naive Brute-Force Approach

The most direct approach to solving this problem is to generate every possible substring, inspect its characters, and check whether all three characters are present.

Algorithm Mechanics

1. Outer loop (i) picks every possible starting index from 0 to n - 1.
2. Inner loop (j) extends the substring from i to n - 1.
3. A frequency hash array of size 3 maps characters (a -> 0, b -> 1, c -> 2).
4. If all elements in the hash array are $\ge 1$, increment our answer counter.

Naive Implementation (Python)

def numberOfSubstrings_brute(s: str) -> int:
    n = len(s)
    count = 0
    
    for i in range(n):
        hash_arr = [0, 0, 0]
        for j in range(i, n):
            hash_arr[ord(s[j]) - ord('a')] += 1
            
            # Check if all characters 'a', 'b', and 'c' are present
            if hash_arr[0] > 0 and hash_arr[1] > 0 and hash_arr[2] > 0:
                count += 1
                
    return count

Complexity Analysis

• Time Complexity: $\mathcal{O}(N^2)$ due to the nested loops exploring all start and end combinations.
• Space Complexity: $\mathcal{O}(1)$ auxiliary space since the hash array is fixed at size 3.

3. Brute-Force Optimization (Early Break Trick)

Before jumping straight to linear time, we can introduce a minor optimization: The moment a valid substring is found at index j, all subsequent extensions further to the right (j+1 to n-1) will also be valid.

String: b  b  a  c  b  a
Index:  0  1  2  3  4  5
             ^  ^
             |  |
      First valid window ends at index 3 ('c').
      All expansions beyond index 3 (indices 4, 5) are also valid!

Optimized Brute-Force Snippet

def numberOfSubstrings_optimized_brute(s: str) -> int:
    n = len(s)
    count = 0
    
    for i in range(n):
        hash_arr = [0, 0, 0]
        for j in range(i, n):
            hash_arr[ord(s[j]) - ord('a')] += 1
            
            if hash_arr[0] > 0 and hash_arr[1] > 0 and hash_arr[2] > 0:
                # Add all remaining substrings from j to n-1
                count += (n - j)
                break  # No need to extend further for this starting index 'i'
                
    return count

While this reduces operations for certain test cases, the worst-case time complexity remains $\mathcal{O}(N^2)$ (e.g., strings consisting of identical characters like aaaa...).

4. Core Mental Model: The Reverse Substring Strategy

To achieve an optimal $\mathcal{O}(N)$ solution, we shift our perspective:

• Instead of asking: "How many substrings start at index i?"
• We ask: "How many valid substrings end at the current character index i?"

Visualizing Ending Substrings

Consider string s = "bacbac", index by index:

Index:  0  1  2  3  4  5
Char:   b  b  a  c  b  a

When our scanning pointer stops at index 3 (character 'c'):

1. We look backward to find the minimum window that contains 'a', 'b', and 'c' ending at index 3.
2. The minimum valid window spans from index 1 to 3 ("bac").
3. Any character to the left of index 1 (indices 0 and down) can also be included while keeping the window valid.
4. Therefore, the number of valid substrings ending at index 3 is equal to index of leftmost boundary + 1 (i.e., 1 + 1 = 2 substrings: "bac" and "bbac").

5. Step-by-Step Execution Walkthrough

Let's trace s = "bacbac" with index tracking:

• Last Seen Array: initialized to [-1, -1, -1] representing positions for [a, b, c].

Total valid substrings = 9.

6. Optimal Linear Time Algorithm Design

By maintaining an array of size 3 (last_seen), we record the most recent index where each character (a, b, or c) appeared. As we iterate through the string:

1. Update the last seen index for the current character.
2. Check if all three characters have been seen at least once (i.e., none of the indices in last_seen equal -1).
3. If valid, add min(last_seen[0], last_seen[1], last_seen[2]) + 1 to our total count.

Production-Ready Implementation (Python)

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        # last_seen stores the most recent index of characters 'a', 'b', and 'c'
        last_seen = [-1, -1, -1]
        count = 0
        
        for i in range(len(s)):
            # Update the last seen index for the current character
            char_idx = ord(s[i]) - ord('a')
            last_seen[char_idx] = i
            
            # If all three characters have appeared at least once
            if last_seen[0] != -1 and last_seen[1] != -1 and last_seen[2] != -1:
                # The minimum index among last_seen marks the start of the shortest valid window
                min_left_index = min(last_seen[0], last_seen[1], last_seen[2])
                
                # Add all valid starting positions from 0 up to min_left_index
                count += (min_left_index + 1)
                
        return count

7. Comparative Approach Synthesis

8. Summary and Key Takeaways

• Problem Reduction: Counting substrings that contain all required elements can be simplified by focusing on where each valid window ends rather than generating every possible start point.
• Last-Seen Array Technique: Keeping a fixed-size tracking array (size = 3) for characters 'a', 'b', and 'c' eliminates the need for hash maps or nested window scans.
• Window Boundary Logic: The minimum index among the last seen positions (min(a, b, c)) defines the tightest valid window ending at the current character.
• Accumulation Formula: Adding min_left_index + 1 at each step correctly counts all valid starting prefixes in $\mathcal{O}(1)$ math operations per character.
• Optimal Performance: The solution achieves $\mathcal{O}(N)$ time complexity and $\mathcal{O}(1)$ space complexity, making it exceptionally efficient for interview settings and production codebases.