Question

2067. Number of Equal Count Substrings

中文文档

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.

 

Example 1:

Input: s = "aaabcbbcc", count = 3
Output: 3
Explanation:
The substring that starts at index 0 and ends at index 2 is "aaa".
The letter 'a' in the substring appears exactly 3 times.
The substring that starts at index 3 and ends at index 8 is "bcbbcc".
The letters 'b' and 'c' in the substring appear exactly 3 times.
The substring that starts at index 0 and ends at index 8 is "aaabcbbcc".
The letters 'a', 'b', and 'c' in the substring appear exactly 3 times.

Example 2:

Input: s = "abcd", count = 2
Output: 0
Explanation:
The number of times each letter appears in s is less than count.
Therefore, no substrings in s are equal count substrings, so return 0.

Example 3:

Input: s = "a", count = 5
Output: 0
Explanation:
The number of times each letter appears in s is less than count.
Therefore, no substrings in s are equal count substrings, so return 0

 

Constraints:

• 1 <= s.length <= 3 * 104
• 1 <= count <= 3 * 104
• s consists only of lowercase English letters.

Solutions

Solution 1

class Solution:
  def equalCountSubstrings(self, s: str, count: int) -> int:
    ans = 0
    for x in range(1, 27):
      m = count * x
      if m > len(s):
        break
      cnt = Counter()
      y = 0
      for i, c in enumerate(s):
        cnt[c] += 1
        y += cnt[c] == count
        y -= cnt[c] == count + 1
        j = i - m
        if j >= 0:
          cnt[s[j]] -= 1
          y += cnt[s[j]] == count
          y -= cnt[s[j]] == count - 1
        ans += x == y
    return ans

class Solution {
  public int equalCountSubstrings(String s, int count) {
    int ans = 0;
    int n = s.length();
    for (int x = 1; x < 27 && count * x <= n; ++x) {
      int m = count * x;
      int[] cnt = new int[26];
      int y = 0;
      for (int i = 0; i < n; ++i) {
        int a = s.charAt(i) - 'a';
        ++cnt[a];
        if (cnt[a] == count) {
          ++y;
        }
        if (cnt[a] == count + 1) {
          --y;
        }
        int j = i - m;
        if (j >= 0) {
          int b = s.charAt(j) - 'a';
          --cnt[b];
          if (cnt[b] == count) {
            ++y;
          }
          if (cnt[b] == count - 1) {
            --y;
          }
        }
        if (x == y) {
          ++ans;
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  int equalCountSubstrings(string s, int count) {
    int ans = 0;
    int n = s.size();
    int cnt[26];
    for (int x = 1; x < 27 && count * x <= n; ++x) {
      int m = count * x;
      memset(cnt, 0, sizeof cnt);
      int y = 0;
      for (int i = 0; i < n; ++i) {
        int a = s[i] - 'a';
        ++cnt[a];
        y += cnt[a] == count;
        y -= cnt[a] == count + 1;
        int j = i - m;
        if (j >= 0) {
          int b = s[j] - 'a';
          --cnt[b];
          y += cnt[b] == count;
          y -= cnt[b] == count - 1;
        }
        ans += x == y;
      }
    }
    return ans;
  }
};

func equalCountSubstrings(s string, count int) (ans int) {
  n := len(s)
  for x := 1; x < 27 && x*count <= n; x++ {
    m := x * count
    y := 0
    cnt := [26]int{}
    for i, c := range s {
      a := c - 'a'
      cnt[a]++
      if cnt[a] == count {
        y++
      }
      if cnt[a] == count+1 {
        y--
      }
      j := i - m
      if j >= 0 {
        b := s[j] - 'a'
        cnt[b]--
        if cnt[b] == count {
          y++
        }
        if cnt[b] == count-1 {
          y--
        }
      }
      if x == y {
        ans++
      }
    }
  }
  return
}

/**
 * @param {string} s
 * @param {number} count
 * @return {number}
 */
var equalCountSubstrings = function (s, count) {
  let ans = 0;
  const n = s.length;
  for (let x = 1; x <= 26 && x * count <= n; ++x) {
    const m = x * count;
    const cnt = new Array(26).fill(0);
    let y = 0;
    for (let i = 0; i < n; ++i) {
      const a = s.charCodeAt(i) - 'a'.charCodeAt(0);
      ++cnt[a];
      y += cnt[a] == count;
      y -= cnt[a] == count + 1;
      const j = i - m;
      if (j >= 0) {
        const b = s.charCodeAt(j) - 'a'.charCodeAt(0);
        --cnt[b];
        y += cnt[b] == count;
        y -= cnt[b] == count - 1;
      }
      ans += x == y;
    }
  }
  return ans;
};