Watch 10 video solutions for Number of Substrings Containing All Three Characters, a medium level problem involving Hash Table, String, Sliding Window. This walkthrough by take U forward has 233,306 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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^4s only consists of a, b or c characters.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 | 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 |