FastPrepCount Equal-Frequency Subsequences
Problems/Count Equal-Frequency Subsequences

Count Equal-Frequency Subsequences

Expedia logoExpedia● MediumNEW GRADOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report describes a dynamic programming task. Given a string word, count the subsequences in which all characters appear the same number of times. The answer is given modulo 10^9+7.

The report gives no examples or limits and does not say how to count. Here, the empty subsequence does not count. Subsequences are counted by the positions chosen, so the same text from different positions counts each time. A character that is not in the subsequence is ignored. The word uses only lowercase English letters. The function shape, the examples, and the limits are our choices, not from the report.

Our version is about 85% the same as the reported question.

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 word that 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) → int

Examples

Example 1

word = "aab"return = 6

Number 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 = 7

Every 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 = 20

With 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 = 511620082

The 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^4
  • word contains 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 New Grad SDE Interviews: 20 Experiences (Part 1 of 3)

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)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int countEqualFrequencySubsequences(String word) {
        // Write your code here.
    }
}
Checking account…