1358: Number-of-Substrings-Containing-All-Three-Characters
Medium

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:

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

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: