Number of Substrings Containing All Three Characters

Med

#1260Time: O(n³). There are O(n²) substrings. For each substring, we perform a check that can take up to O(n) time in the worst case. This leads to a total time complexity of O(n² * n) = O(n³).Space: O(n). In the worst case, a substring of length `n` is created, requiring O(n) space. The check itself can be done with O(1) space, but the substring creation dominates.2 companies

Patterns

Sliding Window

Data structures

Hash Table String

Companies

PayPal DE Shaw

Prompt

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.

Approaches

4 approaches with complexity analysis and trade-offs.

The most straightforward approach is to generate every possible substring of the input string s and then, for each one, check if it contains at least one 'a', one 'b', and one 'c'. We can use two nested loops to define the start and end points of all substrings and a helper function to validate each one.

Algorithm

Initialize a counter count to 0.
Use a nested loop to generate all substrings. The outer loop i iterates from 0 to n-1 (start index).
The inner loop j iterates from i to n-1 (end index).
For each substring s.substring(i, j+1), create a helper function isValid(substring).
The isValid function checks if the substring contains 'a', 'b', and 'c'. This can be done by iterating through the substring and using a Set or three boolean flags.
If isValid returns true, increment count.
After the loops complete, return count.

Walkthrough

This method systematically checks every single substring. The outer loop fixes the starting character of the substring, and the inner loop extends the substring one character at a time to the right. For each generated substring, a separate check is performed to see if it meets the criteria of containing all three characters 'a', 'b', and 'c'.

1class Solution {2    public int numberOfSubstrings(String s) {3        int n = s.length();4        int count = 0;5        for (int i = 0; i < n; i++) {6            for (int j = i; j < n; j++) {7                if (isValid(s.substring(i, j + 1))) {8                    count++;9                }10            }11        }12        return count;13    }14 15    private boolean isValid(String sub) {16        boolean hasA = false;17        boolean hasB = false;18        boolean hasC = false;19        for (char c : sub.toCharArray()) {20            if (c == 'a') hasA = true;21            if (c == 'b') hasB = true;22            if (c == 'c') hasC = true;23            if (hasA && hasB && hasC) return true;24        }25        return false;26    }27}

Complexity

Time

O(n³). There are O(n²) substrings. For each substring, we perform a check that can take up to O(n) time in the worst case. This leads to a total time complexity of O(n² * n) = O(n³).

Space

O(n). In the worst case, a substring of length `n` is created, requiring O(n) space. The check itself can be done with O(1) space, but the substring creation dominates.

Trade-offs

Pros

Simple to understand and implement.
Correctly solves the problem for very small inputs.

Cons

Extremely inefficient due to its cubic time complexity.
Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.

This approach improves upon the naive brute force method by optimizing the validation step. Instead of re-scanning each substring from scratch, we can maintain a running count of the characters 'a', 'b', and 'c' as we extend the substring from a fixed starting point.

Algorithm

Initialize a counter count to 0.
Use an outer loop i from 0 to n-1 to fix the starting point of the substring.
For each i, initialize a frequency count (e.g., an array int[3]) for characters 'a', 'b', 'c'.
Use an inner loop j from i to n-1 to extend the substring to the right.
In the inner loop, update the frequency count for the character s.charAt(j).
After updating, check if the counts for 'a', 'b', and 'c' are all greater than 0.
If they are, it means the substring s.substring(i, j+1) is valid. From this point on, any further extension of the substring from this i will also be valid. So we can add the remaining length n-j to the count and break the inner loop.
Return count after the loops.

Walkthrough

We iterate through all possible starting positions i. For each i, we iterate from j = i to the end of the string, maintaining a count of characters 'a', 'b', and 'c' for the substring s[i...j]. Once the substring s[i...j] contains all three characters, we know it's a valid substring. Furthermore, any substring starting at i and ending after j (i.e., s[i...j+1], s[i...j+2], etc.) will also be valid. There are n - j such substrings. We can add this number to our total count and break the inner loop to move to the next starting position i.

1class Solution {2    public int numberOfSubstrings(String s) {3        int n = s.length();4        int count = 0;5        for (int i = 0; i < n; i++) {6            int[] freq = new int[3]; // 0 for 'a', 1 for 'b', 2 for 'c'7            for (int j = i; j < n; j++) {8                freq[s.charAt(j) - 'a']++;9                if (freq[0] > 0 && freq[1] > 0 && freq[2] > 0) {10                    // All substrings from s[i...j] to s[i...n-1] are valid11                    count += (n - j);12                    break; // Move to the next starting point i13                }14            }15        }16        return count;17    }18}

Complexity

Time

O(n²). We still have two nested loops. Although we have an optimization with `break`, the worst-case scenario (e.g., a string like 'aaaa...aaabc') still requires iterating through most of the O(n²) pairs.

Space

O(1). We only use a constant-size array for frequency counts, regardless of the input string size.

Trade-offs

Pros

More efficient than the naive O(n³) brute force.
Reduces redundant computations by reusing the frequency count.

Cons

Still too slow for the given constraints, leading to 'Time Limit Exceeded'.

A much more efficient approach uses the sliding window technique. The core idea is that if a substring s[i...j] is valid (contains 'a', 'b', 'c'), then any larger substring that contains it, like s[i...k] where k > j, is also valid. We can use this property to count valid substrings in linear time by efficiently expanding and shrinking a window over the string.

Algorithm

Initialize two pointers, left = 0, a result counter count = 0, and a frequency map freq (e.g., an int[3] array).
Iterate with a right pointer from 0 to n-1 to expand the window.
In each iteration, add s.charAt(right) to the window by incrementing its count in freq.
Enter a while loop that runs as long as the current window s[left...right] is valid (i.e., freq['a'] > 0, freq['b'] > 0, and freq['c'] > 0).
Inside the while loop, we've found a minimal valid substring s[left...right]. Any substring starting at left and ending at right or later will also be valid. There are n - right such substrings. Add this number to count.
To find other valid substrings, shrink the window from the left: decrement the frequency of s.charAt(left) and increment left.
The while loop continues to shrink the window as long as it remains valid.
After the main loop over right finishes, return count.

Walkthrough

We maintain a window [left, right] and a frequency count of characters within it. We expand the window by moving right. Once the window contains 'a', 'b', and 'c', we know that the current substring s[left...right] is valid. Crucially, any substring that starts at left and ends at or after right is also valid. There are n - right such substrings. We add this to our total count. Then, we try to find a new, smaller valid window by shrinking it from the left (incrementing left) and updating the frequency count. We repeat this process until the window is no longer valid, at which point we continue expanding with right.

1class Solution {2    public int numberOfSubstrings(String s) {3        int n = s.length();4        int left = 0;5        long count = 0;6        int[] freq = new int[3]; // 0 for 'a', 1 for 'b', 2 for 'c'7 8        for (int right = 0; right < n; right++) {9            freq[s.charAt(right) - 'a']++;10            11            // Once the window is valid, for this fixed 'right', any substring12            // starting from the current 'left' up to 'right' is a valid start.13            // But the logic here is different: we shrink the window.14            while (freq[0] > 0 && freq[1] > 0 && freq[2] > 0) {15                // If s[left...right] is a valid window, then s[left...right], 16                // s[left...right+1], ..., s[left...n-1] are all valid substrings.17                // There are n - right such substrings.18                count += (n - right);19                20                // Now, we shrink the window from the left to see if we can find21                // another valid window with a new 'left'.22                freq[s.charAt(left) - 'a']--;23                left++;24            }25        }26        return (int)count;27    }28}

Complexity

Time

O(n). Both `left` and `right` pointers traverse the string at most once. Each character is added to and removed from the window once, leading to linear time complexity.

Space

O(1). We use a constant-size array for frequency counts.

Trade-offs

Pros

Optimal time complexity of O(n).
Efficiently solves the problem within the given constraints.
Uses constant extra space.

Cons

The logic of counting n - right and shrinking the window can be slightly less intuitive on first sight compared to brute-force methods.

This is an elegant and highly efficient O(n) solution that can be seen as a specialized version of the sliding window. Instead of maintaining a frequency count and two pointers, we simplify the state by just keeping track of the last seen indices of 'a', 'b', and 'c'. This allows for a very clean single-pass solution.

Algorithm

Initialize an array lastSeen of size 3 with -1, to store the most recent index of 'a', 'b', and 'c'.
Initialize a counter count = 0.
Iterate through the string with an index i from 0 to n-1.
At each character s.charAt(i), update the corresponding index in lastSeen to i.
After updating, check if we have seen all three characters (i.e., none of the indices in lastSeen are -1).
If so, a valid substring ending at i must start at or before the character that appeared least recently. This position is min(lastSeen[0], lastSeen[1], lastSeen[2]).
Any substring starting from index 0 up to this minimum index, and ending at i, will be valid. The number of such starting positions is min(lastSeen) + 1.
Add this number to our total count.
After the loop finishes, return count.

Walkthrough

We iterate through the string, and for each position i, we update the last seen index of the character s.charAt(i). As soon as we have seen all three characters, we can calculate how many valid substrings end at the current position i. A substring s[j...i] is valid if it contains all three characters. This is guaranteed if j is less than or equal to the indices of the most recent 'a', 'b', and 'c'. Therefore, j can be any index from 0 up to min(last_a, last_b, last_c). The number of such valid starting points j is min(last_a, last_b, last_c) + 1. By summing this value for each i in the string, we get the total count.

1class Solution {2    public int numberOfSubstrings(String s) {3        // lastSeen[0] for 'a', lastSeen[1] for 'b', lastSeen[2] for 'c'4        int[] lastSeen = {-1, -1, -1};5        int count = 0;6        int n = s.length();7 8        for (int i = 0; i < n; i++) {9            lastSeen[s.charAt(i) - 'a'] = i;10            11            // If we have not seen all three characters yet, we can't form a valid substring.12            if (lastSeen[0] == -1 || lastSeen[1] == -1 || lastSeen[2] == -1) {13                continue;14            }15            16            // Find the minimum index among the last seen positions of a, b, and c.17            // This index is the leftmost boundary of the shortest valid substring ending at i.18            int minIndex = Math.min(lastSeen[0], Math.min(lastSeen[1], lastSeen[2]));19            20            // Any substring starting from index 0 up to minIndex and ending at i will be valid.21            // The number of such substrings is minIndex + 1.22            count += (minIndex + 1);23        }24        25        return count;26    }27}

Complexity

Time

O(n). The algorithm consists of a single loop that iterates through the string once.

Space

O(1). We only use a constant-size array (`lastSeen`) to store three indices.

Trade-offs

Pros

Optimal O(n) time complexity and O(1) space complexity.
Very concise and implemented in a single, clean pass.
Arguably the most elegant and efficient solution.

Cons

The counting logic (min(...) + 1) might require a moment of thought to fully grasp its correctness.

Solutions

Solution

1class Solution {2public3  int numberOfSubstrings(String s) {4    int[] d = new int[]{-1, -1, -1};5    int ans = 0;6    for (int i = 0; i < s.length(); ++i) {7      char c = s.charAt(i);8      d[c - 'a'] = i;9      ans += Math.min(d[0], Math.min(d[1], d[2])) + 1;10    }11    return ans;12  }13}

1class Solution {2public:3  int numberOfSubstrings(string s) {4    int d[3] = {-1, -1, -1};5    int ans = 0;6    for (int i = 0; i < s.size(); ++i) {7      d[s[i] - 'a'] = i;8      ans += min(d[0], min(d[1], d[2])) + 1;9    }10    return ans;11  }12};

1class Solution:2    def numberOfSubstrings(self, s: str) -> int: d = {"a": - 1, "b": - 1, "c": - 1} ans = 0 for i, c in enumerate(s): d[c] = i ans += min(d["a"], d["b"], d["c"]) + 1 return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int numberOfSubstrings(String s) {4    int[] d = new int[]{-1, -1, -1};5    int ans = 0;6    for (int i = 0; i < s.length(); ++i) {7      char c = s.charAt(i);8      d[c - 'a'] = i;9      ans += Math.min(d[0], Math.min(d[1], d[2])) + 1;10    }11    return ans;12  }13}

1class Solution {2public:3  int numberOfSubstrings(string s) {4    int d[3] = {-1, -1, -1};5    int ans = 0;6    for (int i = 0; i < s.size(); ++i) {7      d[s[i] - 'a'] = i;8      ans += min(d[0], min(d[1], d[2])) + 1;9    }10    return ans;11  }12};

1class Solution:2    def numberOfSubstrings(self, s: str) -> int: d = {"a": - 1, "b": - 1, "c": - 1} ans = 0 for i, c in enumerate(s): d[c] = i ans += min(d["a"], d["b"], d["c"]) + 1 return ans

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.