Count Equal-Frequency Subsequences
Updated
Problem statement
You are given a string word. A subsequence comes from choosing one or more positions in word and keeping those characters in their original order.
A subsequence counts when every character that appears in it appears the same number of times.
- A character of
wordthat the subsequence does not use is ignored. - Two subsequences are different when they use different positions, even when they spell the same text.
- The empty subsequence does not count.
Return the number of subsequences that count. The answer can be very large, so return it modulo 10^9 + 7.
Function
countEqualFrequencySubsequences(word: String) → intExamples
Example 1
word = "aab"return = 6Number the positions 1, 2, 3. The choices that count are the single letters at positions 1, 2, and 3, then aa from positions 1 and 2, then ab from positions 1 and 3, and ab from positions 2 and 3. That makes 6. The only other choice is all three positions, aab, which has 2 of a and 1 of b, so it does not count.
Example 2
word = "zzz"return = 7Every choice of positions uses only z, so all choices count. There are 3 single positions, 3 pairs, and 1 triple, which makes 7. They spell only 3 different texts, but the count goes by positions.
Example 3
word = "aabbc"return = 20With each letter used once, a can be skipped or taken in 2 ways, b the same, and c can be skipped or taken in 1 way. That gives 3 x 3 x 2 = 18 choices, and removing the empty one leaves 17.
With each letter used twice, the choices are aa, bb, and aabb, which adds 3. c is not in those three subsequences, and that does not matter. The total is 20.
Example 4
word = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"return = 511620082The word is a repeated 40 times. Every non-empty choice counts, so the exact answer is 2^40 - 1 = 1099511627775. Modulo 10^9 + 7, that is 511620082.
Constraints
1 <= word.length <= 10^4wordcontains only lowercase English letters.
More Expedia Online Assessment questions
- Balanced NumbersOA · Seen Aug 2026
- REST API: Discounted PriceOA · Seen Aug 2026
- Maximum Team SizeOA · Seen Mar 2026
- Per-Domain Request LimiterOA · Seen Oct 2025
- Count Increasing Stock PeriodsOA · Seen Mar 2025
- Get Minimum StepsOA · Seen Oct 2024
- Rank Songs by PopularityOA · Seen Oct 2024
- Calculate the SumOA · Seen Oct 2024
- Get Maximum EfficiencyOA · Seen Oct 2024
- Longest Subsequence That Is a SubstringOA · Seen Oct 2024
Similar questions at other companies
- Count Digit Replacements with No Equal Adjacent DigitsMicrosoft · OAMicrosoft interview questions
- Count One-Swap Number PairsCapital One · OACapital One interview questions
- Longest String ChainVisa · OAVisa interview questions
- How Many Sentences?Chubb · OAChubb interview questions
- Cheating CodemakerJane Street · OAJane Street interview questions
- Replace '?' to Avoid Adjacent DuplicatesSalesforce · OASalesforce interview questions
- Longest String ChainLinkedIn · OALinkedIn interview questions
- How Many Sentences?Atlassian · OAAtlassian interview questions
- Optimize Discount Selection Under a Point BudgetPalantir · OAPalantir interview questions
- Count Phrases Formed by Anagram ReplacementWells Fargo · OAWells Fargo interview questions
Interview reports that mention this question
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)