Number of Substrings Containing All Three Characters

Ah, the classic problem of finding substrings that contain all three characters. It’s like trying to find a unicorn in a haystack, but instead of a mythical creature, you’re just looking for a few letters. Imagine you’re at a party, and you need to find a group of three friends: one who loves pizza, one who can’t stop talking about their cat, and one who insists on wearing socks with sandals. You can’t leave until you find all three together!

In this problem, we’re given a string consisting of only three distinct characters (let’s say ‘a’, ‘b’, and ‘c’), and we need to count how many substrings contain at least one of each character. Sounds simple, right? Well, buckle up, because it’s about to get a little tricky!

Code Solution

class Solution {
 public:
  int numberOfSubstrings(string s) {
    int ans = 0;
    vector count(3);
    int l = 0;
    for (const char c : s) {
      ++count[c - 'a'];
      while (count[0] > 0 && count[1] > 0 && count[2] > 0)
        --count[s[l++] - 'a'];
      ans += l;
    }
    return ans;
  }
};

Approach Explanation

The approach used in this solution is a sliding window technique. We maintain a count of the characters in the current window and expand the window by moving the right pointer. When we find a valid window that contains all three characters, we shrink the window from the left until it no longer contains all three characters. For every valid window, we can count how many substrings end at the current right pointer.

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string. We traverse the string once with two pointers.

Space Complexity: O(1), since we are using a fixed-size array to count the characters.

Real-World Example

Imagine you’re at a buffet, and you need to fill your plate with at least one item from each of the three food groups: veggies, carbs, and protein. You can’t leave until you have a balanced plate! Similarly, in our problem, we need to find all the substrings that contain at least one of each character.