Number of Substrings Containing All Three Characters - Solution & Explanation
Problem Statement
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^4sonly consists of a, b or c characters.
Approach Overview
Problem Overview: Given a string consisting only of characters a, b, and c, count how many substrings contain at least one occurrence of all three characters. The challenge is efficiently identifying valid substrings without checking every possible combination.
Approach 1: Brute Force Enumeration (O(n2) time, O(1) space)
Start each substring at index i and extend it character by character to the right. Maintain a small frequency counter for a, b, and c. As soon as the substring contains all three characters, every longer substring starting at i is also valid, so you can add n - j to the result and stop expanding from that start index. This method is easy to reason about and demonstrates the core observation that once a substring becomes valid, all extensions remain valid. Time complexity is O(n^2) due to the nested expansion, while space remains O(1) because only three counters are stored.
Approach 2: Sliding Window with Character Counts (O(n) time, O(1) space)
The optimal solution uses a sliding window. Maintain two pointers left and right and track frequencies of the three characters using a small array or hash table. Expand the window by moving right. Once the window contains at least one a, b, and c, every substring starting at left and ending at or after right is valid. Add n - right to the result, then shrink the window by moving left and updating counts until the window becomes invalid again.
This works because the string only contains three distinct characters. Each pointer moves at most n times, so the algorithm runs in linear O(n) time with constant O(1) space. The approach is a classic application of the string sliding window pattern where you maintain a window satisfying a condition and count valid expansions efficiently.
Recommended for interviews: The sliding window solution is the expected answer. Interviewers want to see that you recognize the pattern of counting substrings with a dynamic window and constant-size frequency tracking. Mentioning the brute force approach first shows understanding of the problem space, but implementing the O(n) sliding window demonstrates stronger algorithmic optimization skills.
Approach 1: Sliding Window Approach
The sliding window technique is useful in efficiently identifying substrings in a given string. We can maintain a window that keeps track of the number of 'a', 'b', and 'c' characters using a map or counter.
Once the window contains all three characters, we count the number of valid substrings ending at the window's right-end by all possible window left-end positions.
The function maintains a count of each 'a', 'b', and 'c' in the current window using a dictionary. It increments the window's right edge to include each character from the string. If the window contains all three characters, it increments the result by the number of possibilities with the right edge at the current position and then moves the left edge to try and find new valid windows. This process continues until all possible substrings are evaluated.
Complexity
Time Complexity: O(n) - We iterate over the string once.
Space Complexity: O(1) - Constant space is used for the character count.
Approach 2: Brute Force Approach
This straightforward approach checks every possible substring in the string, counts occurrences of 'a', 'b', and 'c', and increments the count of valid substrings. While not optimal, this method verifies the correctness of the problem when considering small inputs or verifying edge cases.
The function generates all substrings from the given string. It uses a helper function to check if the substring contains all characters 'a', 'b', and 'c'. If it does, it contributes to the valid substring count. This approach involves iterating through all possible start and end indices of substrings.
Code
Python
JavaScript
Complexity
Time Complexity: O(n^3) - Due to generation and verification of all possible substrings.
Space Complexity: O(1) - No additional space needed beyond input size.
Approach 3: 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.
We traverse the string s. For the current position i, we first update d[s[i]]=i, then the number of valid strings is min(d[0], d[1], d[2]) + 1, which is accumulated to the answer.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n) - We iterate over the string once. |
| Brute Force Approach | Time Complexity: O(n^3) - Due to generation and verification of all possible substrings. |
| Single Pass | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^2) | O(1) | Good for understanding the problem and validating logic during interviews |
| Sliding Window with Frequency Count | O(n) | O(1) | Optimal solution for large inputs and the expected interview approach |
Video Solution
L7. Number of Substrings Containing All Three Characters | 2 Pointers and Sliding Window Playlist • take U forward • 268,284 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Substrings Containing All Three Characters easy or hard?
Number of Substrings Containing All Three Characters Python/Java solution
How to solve Number of Substrings Containing All Three Characters in O(n)?
What is the best approach for Number of Substrings Containing All Three Characters?
Is Number of Substrings Containing All Three Characters asked at Google/Amazon/Meta?
What data structure is used in Number of Substrings Containing All Three Characters?
What is the time complexity of Number of Substrings Containing All Three Characters?
Ready to solve this problem?
Practice Number of Substrings Containing All Three Characters with our built-in code editor and test cases.
Practice on FleetCode