How hard is LeetCode 2539. Count the Number of Good Subsequences?

LeetCode 2539. Count the Number of Good Subsequences is rated Medium on LeetCode.

What is the time complexity of LeetCode 2539. Count the Number of Good Subsequences?

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

What is the space complexity of LeetCode 2539. Count the Number of Good Subsequences?

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

What topics does LeetCode 2539. Count the Number of Good Subsequences cover?

LeetCode 2539. Count the Number of Good Subsequences is tagged Hash Table, Math, String, Combinatorics and Counting on LeetCode.

Is LeetCode 2539. Count the Number of Good Subsequences a premium problem?

Yes. LeetCode 2539. Count the Number of Good Subsequences is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Count the Number of Good Subsequences — LeetCode 2539 Python Solution

MediumLeetCode PremiumHash TableMathStringCombinatoricsCounting

Problem: #2539
Pattern: Math and Number Theory
Reading time: 4 min
Source: leetcode.com

The problem

A subsequence of a string is good if it is not empty and the frequency of each one of its characters is the same. Given a string s, return the number of good subsequences of s.

Example

Input: s = "aabb"
Output: 11
Explanation: The total number of subsequences is 24. There are five subsequences which are not good: "aabb", "aabb", "aabb", "aabb", and the empty subsequence. Hence, the number of good subsequences is 24-5 = 11.

Python solution

Python

N = 10001
MOD = 10**9 + 7
f = [1] * N
g = [1] * N
for i in range(1, N):
    f[i] = f[i - 1] * i % MOD
    g[i] = pow(f[i], MOD - 2, MOD)


def comb(n, k):
    return f[n] * g[k] * g[n - k] % MOD


class Solution:
    def countGoodSubsequences(self, s: str) -> int:
        cnt = Counter(s)
        ans = 0
        for i in range(1, max(cnt.values()) + 1):
            x = 1
            for v in cnt.values():
                if v >= i:
                    x = x * (comb(v, i) + 1) % MOD
            ans = (ans + x - 1) % MOD
        return ans

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 2539. Count the Number of Good Subsequences is filed here because LeetCode tags it Math and Combinatorics, which is the vocabulary this hub collects.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Frequently asked questions

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