Skip to content

Practice Count The Number of Winning Sequences

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Hard#3320
LeetCode Problem

Count The Number of Winning Sequences

Problem Statement

Alice plays the moves in s, one move per round. F means fire, W means water, and E means earth. Fire defeats earth, water defeats fire, and earth defeats water. A winning move earns one point; equal moves award neither player a point. Bob chooses his moves but cannot repeat a move in consecutive rounds. Count Bob's possible sequences whose total score exceeds Alice's, modulo 1,000,000,007. Approach: Track the previous move and Bob's score minus Alice's score after each round. Extend each state with either different move, adding +1, 0, or -1 according to the matchup. Sum states with a positive final difference. Rolling the round dimension gives O(n^2) time and O(n) space.

Source: Count The Number of Winning Sequences on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
s = "FW"
Output
2
Explanation

Only FE and WE give Bob a strictly positive final score without repeating a move.

# Example 2

Input
s = "E"
Output
1
Explanation

Bob must choose F to win; E ties and W loses.

Constraints

1 <= s.length <= 1000
Every character is F, W, or E.

How to solve Count The Number of Winning Sequences

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

After any round, only Bob's last move and the current score difference matter for the future, so counting sequences is a dynamic program over (last move, difference) states, with the difference offset to stay nonnegative.

Why brute force is not enough

Enumerating Bob's sequences gives 3 times 2^(n - 1) possibilities, astronomically many for lengths up to 1000.

Approach

  1. Encode the matchup as +1 when Bob's move beats Alice's (water over fire, fire over earth, earth over water), -1 when it loses, and 0 on a tie.
  2. Keep a table indexed by Bob's previous move and by the difference Bob minus Alice shifted by n, so values from -n to n map to 0 through 2n. Each cell counts sequences so far ending in that move with that difference, modulo 1,000,000,007.
  3. Seed round one: each of the three moves gets count 1 at the difference it produces against Alice's first move.
  4. For each later round build a fresh table: from every nonzero cell try the two moves different from the previous one, compute the new difference, and add the count. Keep only two rounds alive.
  5. After the last round, sum cells with strictly positive difference modulo 1,000,000,007.

Walkthrough of Example 1

s = "FW" → 2

  1. s is "FW". Round 1 Alice plays F: Bob's F ties (difference 0), W wins (+1), E loses (-1), each count 1.
  2. Round 2 Alice plays W. From F at 0: W ties giving 0, E beats W giving +1.
  3. From W at +1: F loses to W giving 0, E wins giving +2.
  4. From E at -1: F loses giving -2, W ties giving -1.
  5. Positive cells are (E, +1) and (E, +2), each with count 1, total 2, the expected output for FE and WE.

Time and space

Time O(n^2) · Space O(n). With n rounds, each round touches 3 moves times 2n + 1 differences with two transitions each; rolling the round dimension keeps two tables of about 6n cells.

Interview pitfalls

  • Indexing the difference without an offset and dropping negative differences.
  • Letting Bob repeat his previous move, or applying the no-repeat rule to Alice.
  • Reversing the beats relation, for instance fire over water.
  • Counting difference zero as a win; only strictly positive qualifies.
  • Updating the table in place so counts added this round get extended again within it.

Follow-up questions interviewers ask

  • What if Bob may repeat a move but never three times in a row?
  • Can you shrink memory by noting the reachable difference range grows by one per round?
  • What if Alice's moves were unknown and you summed over all her sequences too?

Further reading on the technique: Dynamic programming

Related LeetCode Problems

Practice more problems similar to Count The Number of Winning Sequences.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.