Number of Substrings Containing All Three Characters

MEDIUM

Description

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

Checkout 4 different approaches to solve Number of Substrings Containing All Three Characters. Click on different approaches to view the approach and algorithm in detail.

Brute Force Enumeration

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.

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 Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Number of Substrings Containing All Three Characters. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Number of Substrings Containing All Three Characters

Patterns:

Sliding Window

Data Structures:

Hash TableString

Companies:

PayPal |DE Shaw |