GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing leetcodejavascript.com — #2067 - Number of Equal Count Substrings - LeetCode JavaScript Solutions

Back to all solutions

#2067 - Number of Equal Count Substrings

Medium • View on LeetCode • View on GitHub

String Hash Table Counting Sliding Window

Problem Description

You are given a 0-indexed string s consisting of only lowercase English letters, and an integer count. A substring of s is said to be an equal count substring if, for each unique letter in the substring, it appears exactly count times in the substring.

Return the number of equal count substrings in s.

A substring is a contiguous non-empty sequence of characters within a string.

Solution

/**
 * @param {string} s
 * @param {number} count
 * @return {number}
 */
var equalCountSubstrings = function(s, count) {
  const n = s.length;
  let result = 0;

  for (let uniqueChars = 1; uniqueChars <= 26; uniqueChars++) {
    const targetLength = uniqueChars * count;
    if (targetLength > n) break;

    const charCount = new Map();
    let validChars = 0;

    for (let right = 0; right < n; right++) {
      const rightChar = s[right];
      charCount.set(rightChar, (charCount.get(rightChar) || 0) + 1);

      if (charCount.get(rightChar) === count) {
        validChars++;
      } else if (charCount.get(rightChar) === count + 1) {
        validChars--;
      }

      if (right >= targetLength) {
        const leftChar = s[right - targetLength];
        if (charCount.get(leftChar) === count) {
          validChars--;
        } else if (charCount.get(leftChar) === count + 1) {
          validChars++;
        }

        charCount.set(leftChar, charCount.get(leftChar) - 1);
        if (charCount.get(leftChar) === 0) {
          charCount.delete(leftChar);
        }
      }

      if (right >= targetLength - 1 && validChars === uniqueChars
          && charCount.size === uniqueChars) {
        result++;
      }
    }
  }

  return result;
};

You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.