Scale Engineer

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 TableString
Companies
PayPalDE 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

  1. Initialize a counter count to 0.
  2. Use a nested loop to generate all substrings. The outer loop i iterates from 0 to n-1 (start index).
  3. The inner loop j iterates from i to n-1 (end index).
  4. For each substring s.substring(i, j+1), create a helper function isValid(substring).
  5. 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.
  6. If isValid returns true, increment count.
  7. 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'.

class Solution {    public int numberOfSubstrings(String s) {        int n = s.length();        int count = 0;        for (int i = 0; i < n; i++) {            for (int j = i; j < n; j++) {                if (isValid(s.substring(i, j + 1))) {                    count++;                }            }        }        return count;    }     private boolean isValid(String sub) {        boolean hasA = false;        boolean hasB = false;        boolean hasC = false;        for (char c : sub.toCharArray()) {            if (c == 'a') hasA = true;            if (c == 'b') hasB = true;            if (c == 'c') hasC = true;            if (hasA && hasB && hasC) return true;        }        return false;    }}

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.

Solutions

class Solution {public  int numberOfSubstrings(String s) {    int[] d = new int[]{-1, -1, -1};    int ans = 0;    for (int i = 0; i < s.length(); ++i) {      char c = s.charAt(i);      d[c - 'a'] = i;      ans += Math.min(d[0], Math.min(d[1], d[2])) + 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 →

Next problem