How hard is LeetCode 2067. Number of Equal Count Substrings?

LeetCode 2067. Number of Equal Count Substrings is rated Medium on LeetCode.

What is the time complexity of LeetCode 2067. Number of Equal Count Substrings?

The Python solution on this page runs in O(n \times C).

What is the space complexity of LeetCode 2067. Number of Equal Count Substrings?

The Python solution on this page uses O(C) auxiliary space.

What topics does LeetCode 2067. Number of Equal Count Substrings cover?

LeetCode 2067. Number of Equal Count Substrings is tagged Hash Table, String, Counting and Sliding Window on LeetCode.

Is LeetCode 2067. Number of Equal Count Substrings a premium problem?

Yes. LeetCode 2067. Number of Equal Count Substrings is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Number of Equal Count Substrings — LeetCode 2067 Python Solution

MediumLeetCode PremiumHash TableStringCountingSliding Window

Problem: #2067
Pattern: Sliding Window
Reading time: 4 min
Source: leetcode.com

The problem

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.

Example

Input: s = "aaabcbbcc", count = 3
Output: 3
Explanation: The substring that starts at index 0 and ends at index 2 is "aaa".

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(n \times C)
Space	O(C) auxiliary

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2067. Number of Equal Count Substrings is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2067. Number of Equal Count Substrings?: LeetCode 2067. Number of Equal Count Substrings is rated Medium on LeetCode.
What is the time complexity of LeetCode 2067. Number of Equal Count Substrings?: The Python solution on this page runs in O(n \times C).
What is the space complexity of LeetCode 2067. Number of Equal Count Substrings?: The Python solution on this page uses O(C) auxiliary space.
What topics does LeetCode 2067. Number of Equal Count Substrings cover?: LeetCode 2067. Number of Equal Count Substrings is tagged Hash Table, String, Counting and Sliding Window on LeetCode.
Is LeetCode 2067. Number of Equal Count Substrings a premium problem?: Yes. LeetCode 2067. Number of Equal Count Substrings is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.