Katkat
Back

Count Good Subsequences With Equal Character Frequencies

HackerRankMachine Learning Engineer · Online Assessment
MediumMachine Learning EngineerOnline AssessmentCoding & Algorithms

Last updated

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