Number of Substrings Containing All Three Characters solution and explanation
Google
9 more videos on this problem
L7. Number of Substrings Containing All Three Characters | 2 Pointers and Sliding Window Playlisttake U forward · 19:40 · 268K views
Number of Substrings Containing All Three Characters | Dry Runs | Leetcode 1358 | codestorywithMIKcodestorywithMIK · 20:41 · 16K views
Number of Substrings Containing All Three Characters - Leetcode 1358 - PythonNeetCodeIO · 15:03 · 14K views
1358. Number of Substrings Containing All Three Characters | leetcode daily challenge dsa shashcodeShashCode · 13:14 · 4K views
Number of Substrings Containing All Three Characters | Leetcode 1358Techdose · 19:55 · 3K views
1358. Number of Substrings Containing All Three Characters | Two PointersAryan Mittal · 9:20 · 2K views
Number of Substrings Containing All Three Characters 🔥 Leetcode 1358 | Medium Problem Study Placement · 18:28 · 519 views
Daily Leetcode #1806: Mar 11, 2025 - 1358. Number of Substrings Containing All Three CharactersProgramming Live with Larry · 7:32 · 366 views
Number of Substrings Containing All Three Characters | LeetCode 1358 - Pythonimpoldev · 9:14 · 300 views
1358. Number of Substrings Containing All Three Characters | Leetcode Daily - PythonLeetcode Daily · 4:13 · 262 views
The problem
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.
def number_of_substrings(s):
count = { 'a': 0, 'b': 0, 'c': 0 }
res = 0
left = 0
for right in range(len(s)):
count[s[right]] += 1
while all(count[ch] >= 1 for ch in 'abc'):
res += len(s) - right
count[s[left]] -= 1
left += 1
return resclass Solution {
public int numberOfSubstrings(String s) {
int[] count = {0, 0, 0};
int n = s.length();
int res = 0;
int left = 0;
for (int right = 0; right < n; right++) {
count[s.charAt(right) - 'a']++;
while (count[0] > 0 && count[1] > 0 && count[2] > 0) {
res += n - right;
count[s.charAt(left) - 'a']--;
left++;
}
}
return res;
}
}#include <string>
#include <unordered_map>
class Solution {
public:
int numberOfSubstrings(std::string s) {
std::unordered_map<char, int> count = {{'a', 0}, {'b', 0}, {'c', 0}};
int res = 0, left = 0, n = s.size();
for (int right = 0; right < n; ++right) {
count[s[right]]++;
while (count['a'] > 0 && count['b'] > 0 && count['c'] > 0) {
res += n - right;
count[s[left]]--;
left++;
}
}
return res;
}
};function numberOfSubstrings(s) {
let count = {a: 0, b: 0, c: 0};
let res = 0;
let left = 0;
for (let right = 0; right < s.length; right++) {
count[s[right]]++;
while (count['a'] > 0 && count['b'] > 0 && count['c'] > 0) {
res += s.length - right;
count[s[left]]--;
left++;
}
}
return res;
}#include <stdio.h>
#include <string.h>
int numberOfSubstrings(char* s) {
int count[3] = {0};
int n = strlen(s);
int res = 0, left = 0;
for (int right = 0; right < n; ++right) {
count[s[right] - 'a']++;
while (count[0] > 0 && count[1] > 0 && count[2] > 0) {
res += n - right;
count[s[left] - 'a']--;
left++;
}
}
return res;
}public class Solution {
public int NumberOfSubstrings(string s) {
int[] count = new int[3];
int n = s.Length;
int res = 0, left = 0;
for (int right = 0; right < n; right++) {
count[s[right] - 'a']++;
while (count[0] > 0 && count[1] > 0 && count[2] > 0) {
res += n - right;
count[s[left] - 'a']--;
left++;
}
}
return res;
}
}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.
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.
def number_of_substrings_brute(s):
def has_all_characters(subs):
return 'a' in subs and 'b' in subs and 'c' in subs
res = 0
n = len(s)
for i in range(n):
for j in range(i + 1, n + 1):
if has_all_characters(s[i:j]):
res += 1
return resfunction numberOfSubstringsBrute(s) {
function hasAllCharacters(subs) {
return subs.includes('a') && subs.includes('b') && subs.includes('c');
}
let res = 0;
let n = s.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j <= n; j++) {
if (hasAllCharacters(s.slice(i, j))) {
res++;
}
}
}
return res;
}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.
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).
func numberOfSubstrings(s string) (ans int) {
d := [3]int{-1, -1, -1}
for i, c := range s {
d[c-'a'] = i
ans += min(d[0], min(d[1], d[2])) + 1
}
return
}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 | – |
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 |
Frequently asked questions
Is Number of Substrings Containing All Three Characters easy or hard?
The problem is rated Medium because it requires recognizing the sliding window counting trick. Once you understand how to count all valid extensions using n - right, the implementation becomes straightforward.
Number of Substrings Containing All Three Characters Python/Java solution
Implement the sliding window pattern using two pointers and a frequency map or array. Update counts when expanding the right pointer and shrink from the left once all three characters appear. The same logic works across Python, Java, C++, and JavaScript with O(n) time complexity.
How to solve Number of Substrings Containing All Three Characters in O(n)?
Use a sliding window with two pointers. Expand the right pointer while updating counts of 'a', 'b', and 'c'. Once the window contains all three characters, every longer substring ending to the right is valid, so add n - right to the result and move the left pointer to shrink the window.
What is the best approach for Number of Substrings Containing All Three Characters?
The sliding window approach is the most efficient solution. Maintain two pointers and track counts of 'a', 'b', and 'c'. When the window contains all three characters, add n - right to the result and shrink the window. This runs in O(n) time with O(1) extra space.
Is Number of Substrings Containing All Three Characters asked at Google/Amazon/Meta?
Substring counting and sliding window problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of this problem test whether candidates recognize patterns such as maintaining a valid window and counting substrings efficiently.
What data structure is used in Number of Substrings Containing All Three Characters?
The solution typically uses a small frequency array or hash table to track counts of the characters 'a', 'b', and 'c'. Combined with the sliding window technique, this allows constant-time updates and checks as the window expands or shrinks.
What is the time complexity of Number of Substrings Containing All Three Characters?
The optimal sliding window solution runs in O(n) time because each pointer moves through the string at most once. Space complexity is O(1) since only three character counters are stored. A brute force approach that checks substrings can take O(n^2) time.