Leetcode problem 109 - Number of Substrings Containing All Three Characters

AGiven 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.

/**
 * @param {string} s
 * @return {number}
 */
var numberOfSubstrings = function (s) {
  // Initialize count to keep track of the number of valid substrings
  let count = 0;
  let left = 0;
  let right = 0;

  // Initialize a counter object to keep track of the occurrences of 'a', 'b', and 'c' in the current window
  let charCount = { a: 0, b: 0, c: 0 };

  // Iterate through the characters in the string using the sliding window approach
  while (right < s.length) {
    // Increment the count of the current character in the charCount object
    charCount[s[right]]++;

    // Check if the current window contains at least one occurrence of 'a', 'b', and 'c'
    while (charCount["a"] > 0 && charCount["b"] > 0 && charCount["c"] > 0) {
      // Decrement the count of the character at the left pointer and move the left pointer to the right
      charCount[s[left]]--;
      left++;
    }

    // Add the current value of the left pointer to the count
    // This accounts for the substrings ending at the current 'right' index that contain at least one 'a', 'b', and 'c'
    count += left;

    // Move the right pointer to the next character in the string
    right++;
  }

  // Return the total count of valid substrings
  return count;
};

The time complexity of this code is O(n), where n is the length of the input string. This is because we iterate through the characters of the string using the sliding window approach, and each character is visited once.

The space complexity of this code is O(1), because the space used by the charCount object is constant and does not depend on the size of the input string.