Is Count the Number of Good Subsequences easy or hard?

This problem is generally classified as medium difficulty. The challenge is recognizing that enumerating subsequences is infeasible and converting the problem into a combinatorics counting task based on character frequencies.

Count the Number of Good Subsequences Python/Java solution

The typical implementation counts character frequencies, precomputes factorials and modular inverses, and iterates possible frequency values k. For each k, compute the product of (C(freq[i], k) + 1) across characters and subtract one. The same logic works in Python, Java, C++, and Go using modular arithmetic.

How to solve Count the Number of Good Subsequences in O(n)?

First count character frequencies using a hash map or fixed array of size 26. Precompute factorials and inverse factorials to evaluate C(n, k). For each possible frequency k from 1 to maxFreq, multiply (C(freq[i], k) + 1) for every character and subtract one to exclude the empty subsequence.

What is the best approach for Count the Number of Good Subsequences?

The most efficient approach uses frequency counting combined with combinatorics. Count occurrences of each character, iterate possible frequencies k, and compute combinations C(freq, k) for each character. Multiply choices across characters and subtract the empty case. This runs in O(26 * maxFreq) time with O(n) preprocessing for factorials.

Is Count the Number of Good Subsequences asked at Google/Amazon/Meta?

Problems involving combinatorics, frequency counting, and subsequence counting frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that combine hash tables with combinatorial counting are common medium-level interview questions.

What data structure is used in Count the Number of Good Subsequences?

A frequency map (often an array of size 26 for lowercase letters) stores character counts. The algorithm also relies on combinatorics utilities such as factorial and inverse factorial arrays to compute binomial coefficients efficiently.

What is the time complexity of Count the Number of Good Subsequences?

The optimal solution runs in O(26 * maxFreq) time, where maxFreq is the maximum frequency of any character in the string. Combination values are computed using precomputed factorials and modular inverses, which require O(n) preprocessing space and time.

Description Hints 3 Solution Video 15:27

2539. Count the Number of Good Subsequences

Medium47.7% acceptance4 companiesPremium elsewhere, free here

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. Since the answer may be too large, return it modulo 10⁹ + 7.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

Example 1:

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

Example 2:

Input: s = "leet"
Output: 12
Explanation: There are four subsequences which are not good: "leet", "leet", "leet", and the empty subsequence. Hence, the number of good subsequences is 2⁴-4 = 12.

Example 3:

Input: s = "abcd"
Output: 15
Explanation: All of the non-empty subsequences are good subsequences. Hence, the number of good subsequences is 2⁴-1 = 15.

Constraints:

1 <= s.length <= 10⁴
s consists of only lowercase English letters.

Asked at 4 companies

TuSimple UKG NVIDIA Palantir

Topics

Hints open one at a time

Hint 1

Use the frequency array of characters of the string.

Hint 2

For 1 ≤ m ≤ s.length, count the number of subsequences of s where each character occurs exactly m times.

Hint 3

For any n and k, you can calculate (n choose k) mod p in O(log p) using binary exponentiation.

15:27

Still stuck?Read the written solution, or watch a walkthrough.

Open solution