cswork / libraryOpen practice workspace

Coding questions · HackerRank

Count Good Subsequences With Equal Character Frequencies

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.

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:

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:

word = 'abca'
Output: 12

word = 'abcd'
Output: 15

Count Good Subsequences

Count non-empty subsequences where every selected character appears the same number of times. Different index selections count separately.

Hints

  1. Group subsequences by their common selected frequency.
  2. For a character with count c, choosing f copies has C(c, f) choices.