Number Of Substrings Containing All Three Characters - Leetcode Solution

Problem:

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.

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","abc"].

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","acb"].

Approach:

We can take two pointers left and right, and initialize them with 0. We will also define a variable count which will be used to count the number of substrings that contains at least one occurrence of the characters 'a', 'b', and 'c'. Then we will start moving the right pointer towards the right and keep track of the characters seen so far using a dictionary. If we have seen all three characters at least once, then we will increment the count by the number of characters between left and right. Now we can start moving the left pointer towards the right and decrease the frequency of the character that is moving out of the window. We will repeat this until we have seen all the characters again and keep on updating the count.

Algorithm:

1. Initialize two pointers left and right with 0. Also, initialize the count variable as 0.

2. Create a dictionary to keep track of the frequency of characters in the window.

3. Now start moving the right pointer towards the right, and for each character update the frequency in the dictionary.

4. If we have seen all the characters at least once, increment the count variable by the number of characters between left and right.

5. Now, start moving the left pointer towards the right and decrease the frequency of the character that is moving out of the window.

6. Repeat step 4 and 5 until we have seen all the characters again.

7. Finally, return the count variable as the answer.

Here is the Python code implementing the above algorithm:

def numberOfSubstrings(s):

n = len(s)
char_freq = {}
left = right = count = 0

while right < n:
    char_freq[s[right]] = char_freq.get(s[right], 0) + 1
    if len(char_freq) == 3:
        count += n - right
        while len(char_freq) == 3:
            char_freq[s[left]] -= 1
            if char_freq[s[left]] == 0:
                del char_freq[s[left]]
            left += 1
        count += left - 1
    
    right += 1

return count

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

1