Number of Substrings Containing All Three Characters

This question is just yesterday's question, but not on steroids.

This is a sliding window solution so there do exist 2 pointers; l and r.

During every iteration of our algorithm, we want to:

• extend the r side of the sliding window until we have a sliding window with unique_letters == 3
• then, if unique_letters == 3 is true, we can increment add s.size()-r+1 to ans
  • this is because, we know that extending the window past index r will always return a valid substring
• finally, we can remove s[l] from our counter and increment l
  • this is because, we have already calculated the number of valid substrings starting from index l, so now we can do so for index l+1 and more

Now, the conditions for the iterations to stop should clearly be when:

• r >= s.size() since then, there are no more letters in s to iterate through
• unique_letters < 3 since then, there are no more possible valid substrings
  • this is because, we could theoretically reach r >= s.size(), however, since unique_letters == 3, it means that there potentially still exists valid substrings after incrementing l

Finally, all that we have to do afterwards is just return ans.

code

class Solution {
public:
    int numberOfSubstrings(string s) {
        int unique_letters = 0;
        int letter_count[3] = {0};

        int ans = 0;
        for (int l = 0, r = 0; r < s.size() || unique_letters == 3; ++l) {
            for (; r < s.size() && unique_letters < 3; ++r) {
                if (letter_count[s[r]-'a']++ == 0) {
                    ++unique_letters;
                }
            }

            if (unique_letters == 3) ans += s.size()-r+1;

            if (--letter_count[s[l]-'a'] == 0) {
                --unique_letters;
            }
        }
        return ans;
    }
};

complexity

• Time: O(n)
• Space: O(1)