Count Good Subsequences With Equal Character Frequencies
Company: Hackerrank
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
A subsequence is formed by deleting zero or more characters from a string without changing the order of the remaining characters. A non-empty subsequence is good if every character that appears in it appears the same number of times. Given a lowercase string, return the number of good subsequences modulo `1_000_000_007`.
Function signature:
```python
def count_good_subsequences(word: str) -> int:
pass
```
Constraints:
- `1 <= len(word) <= 100000`.
- `word` contains lowercase English letters.
- The empty subsequence is not good.
- Different index choices count as different subsequences even if they form the same string.
- Return the answer modulo `1_000_000_007`.
Examples:
```text
word = 'abca'
Output: 12
```
```text
word = 'abcd'
Output: 15
```
Quick Answer: Practice a combinatorics coding problem that counts good subsequences where every selected character has the same frequency. The prompt targets frequency counting, combinations, modular arithmetic, and grouping subsequences by common selected count.
Count non-empty subsequences where every selected character appears the same number of times. Different index selections count separately.
Constraints
- The input contains lowercase English letters.
- Return the answer modulo 1_000_000_007.
Examples
Input: ('abca')
Expected Output: 12
Input: ('abcd')
Expected Output: 15
Hints
- Group subsequences by their common selected frequency.
- For a character with count c, choosing f copies has C(c, f) choices.