1358. Number of Substrings Containing All Three Characters

Description

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

 

Solutions

Solution: Sliding Window

• Time complexity: O(n)
• Space complexity: O(3 -> 1)

 

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
const numberOfSubstrings = function (s) {
  const n = s.length;
  const charMap = new Map();
  let left = 0;
  let result = 0;

  for (let index = 0; index < n; index++) {
    const char = s[index];
    const count = charMap.get(char) ?? 0;

    charMap.set(char, count + 1);

    if (charMap.size < 3) continue;

    while (charMap.get(s[left]) > 1) {
      const leftCount = charMap.get(s[left]);

      charMap.set(s[left], leftCount - 1);
      left += 1;
    }

    result += left + 1;
  }

  return result;
};