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 countMap = { a: 0, b: 0, c: 0 };
  let left = 0;
  let result = 0;

  for (let index = 0; index < n; index++) {
    const char = s[index];

    countMap[char] += 1;

    while (countMap.a && countMap.b && countMap.c) {
      const current = s[left];

      countMap[current] -= 1;
      left += 1;
    }

    result += left;
  }

  return result;
};