Skip to main content
Talentd

Count The Number of Winning Sequences - Solution & Explanation

HardStringDynamic Programming17 min readAsked at: Google
Practice this problem

Problem Statement

Alice and Bob are playing a fantasy battle game consisting of n rounds where they summon one of three magical creatures each round: a Fire Dragon, a Water Serpent, or an Earth Golem. In each round, players simultaneously summon their creature and are awarded points as follows:

  • If one player summons a Fire Dragon and the other summons an Earth Golem, the player who summoned the Fire Dragon is awarded a point.
  • If one player summons a Water Serpent and the other summons a Fire Dragon, the player who summoned the Water Serpent is awarded a point.
  • If one player summons an Earth Golem and the other summons a Water Serpent, the player who summoned the Earth Golem is awarded a point.
  • If both players summon the same creature, no player is awarded a point.

You are given a string s consisting of n characters 'F', 'W', and 'E', representing the sequence of creatures Alice will summon in each round:

  • If s[i] == 'F', Alice summons a Fire Dragon.
  • If s[i] == 'W', Alice summons a Water Serpent.
  • If s[i] == 'E', Alice summons an Earth Golem.

Bob’s sequence of moves is unknown, but it is guaranteed that Bob will never summon the same creature in two consecutive rounds. Bob beats Alice if the total number of points awarded to Bob after n rounds is strictly greater than the points awarded to Alice.

Return the number of distinct sequences Bob can use to beat Alice.

Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: s = "FFF"

Output: 3

Explanation:

Bob can beat Alice by making one of the following sequences of moves: "WFW", "FWF", or "WEW". Note that other winning sequences like "WWE" or "EWW" are invalid since Bob cannot make the same move twice in a row.

Example 2:

Input: s = "FWEFW"

Output: 18

Explanation:

Bob can beat Alice by making one of the following sequences of moves: "FWFWF", "FWFWE", "FWEFE", "FWEWE", "FEFWF", "FEFWE", "FEFEW", "FEWFE", "WFEFE", "WFEWE", "WEFWF", "WEFWE", "WEFEF", "WEFEW", "WEWFW", "WEWFE", "EWFWE", or "EWEWE".

 

Constraints:

  • 1 <= s.length <= 1000
  • s[i] is one of 'F', 'W', or 'E'.

Approach Overview

Problem Overview: You are given a string representing Alice’s moves in a cyclic battle game (Fire, Water, Earth). Bob chooses his own sequence of moves but cannot repeat the same move consecutively. A move wins, loses, or draws based on the cyclic rule (F beats E, E beats W, W beats F). The task is to count how many valid sequences Bob can play so that his final score is strictly greater than Alice’s.

Approach 1: Recursive Backtracking with Memoization (O(n^2) time, O(n^2) space)

Model the game round by round. At index i, Bob chooses one of three moves except the move used in the previous round. Each choice changes the score difference depending on whether Bob wins, loses, or draws against Alice’s move. The recursive state becomes (i, lastMove, scoreDiff). Since the score difference ranges roughly from -n to +n, caching results with memoization prevents recomputation. This turns an exponential search into about O(n * 3 * 2n) states. Use recursion plus a hash/map or 3‑D DP array to store computed states.

Approach 2: Dynamic Programming (O(n^2) time, O(n^2) space)

Convert the recursion into bottom‑up dynamic programming. Track dp[i][last][diff], the number of ways after processing i rounds where Bob’s last move is last and the score difference equals diff. For each position, iterate through the three possible moves and skip the one equal to last. Compute the round outcome against Alice’s move and update the next score difference. Because the score difference may be negative, shift the index by +n when storing it. After processing all characters of the string, sum all states where the final difference is positive.

This approach works well because the number of possible score differences grows linearly with the number of rounds, keeping the state space manageable. The transitions are simple constant‑time updates, making the overall complexity about O(n^2). The DP formulation also avoids recursion overhead and is easier to optimize in Python or JavaScript.

Recommended for interviews: Start by describing the recursive state and transitions using dynamic programming. Then convert it into a bottom‑up DP table for clarity and performance. Interviewers typically expect the DP state (index, lastMove, scoreDiff) and a complexity around O(n^2). The memoized recursion shows understanding of the state space, while the iterative DP demonstrates strong implementation skills.

Approach 1: Dynamic Programming Approach

The fundamental observation is that Bob will summon sequences with the following constraints:

  • He cannot summon the same creature in consecutive rounds.
  • He needs to win more rounds than Alice.

We use dynamic programming to track how many ways Bob can schedule his creatures over the rounds to beat Alice.

Use a DP table dp[i][b] where i is the round number and b is the last creature Bob used. This helps to track winning sequences with the last creature being 'F', 'W', or 'E'.

This solution uses a 3D dynamic programming table where each dimension is interpreted as:

  • dp[a][i][b]: Number of ways to beat Alice given last move was creature b up to round i.
  • The transitions account for changes based on Alice's moves and ensure Bob's constraints.

The result is computed by summing up all possible ways Bob can arrange his creatures to have more points than Alice.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n) where n is the length of string s.
Space Complexity: O(n) due to the size of the DP table.

Try this approach in the editor →

Approach 2: Recursive Backtracking with Memoization

This approach involves using a recursive function to simulate Bob's choices. We apply memoization to store results of previously calculated states to avoid redundant calculations.

The function considers the previous move and current round and checks all valid creature choices Bob can make such that he beats Alice's current round choice. We use a map to store the memoized values for states already computed.

In this recursive solution with memoization in C++, we explore each possible move by Bob using backtracking, checking all valid transitions from the previous move to ensure Bob never repeats a move in consecutive rounds. Memoization reduces repeated calculations of previously explored states and optimizes the algorithm.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(n * 3^2) where n is the length of string s.
Space Complexity: O(n * 3 * 2) for memo storage.

Try this approach in the editor →

Approach 3: Memoization Search

We design a function dfs(i, j, k), where i represents starting from the i-th character of the string s, j represents the current score difference between Alice and Bob, and k represents the last creature summoned by Bob. The function calculates how many sequences of moves Bob can make to defeat Alice.

The answer is dfs(0, 0, -1), where -1 indicates that Bob has not summoned any creatures yet. In languages other than Python, since the score difference can be negative, we can add n to the score difference to ensure it is non-negative.

The calculation process of the function dfs(i, j, k) is as follows:

  • If n - i leq j, then the remaining rounds are not enough for Bob to surpass Alice's score, so return 0.
  • If i geq n, then all rounds have ended. If Bob's score is less than 0, return 1; otherwise, return 0.
  • Otherwise, we enumerate the creatures Bob can summon this round. If the creature summoned this round is the same as the one summoned in the previous round, Bob cannot win this round, so we skip it. Otherwise, we recursively calculate dfs(i + 1, j + calc(d[s[i]], l), l), where calc(x, y) represents the outcome between x and y, and d is a mapping that maps characters to 012. We sum all the results and take the modulo 10^9 + 7.

The time complexity is O(n^2 times k^2), where n is the length of the string s, and k represents the size of the character set. The space complexity is O(n^2 times k).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n) where n is the length of string s.
Space Complexity: O(n) due to the size of the DP table.

Recursive Backtracking with Memoization

Time Complexity: O(n * 3^2) where n is the length of string s.
Space Complexity: O(n * 3 * 2) for memo storage.

Memoization Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Backtracking with MemoizationO(n^2)O(n^2)When deriving the solution from game simulation and exploring the state space naturally with recursion.
Dynamic Programming (Score Difference DP)O(n^2)O(n^2)Best general solution. Efficient for n up to typical constraints and avoids recursion overhead.

Video Solution

Dynamic Programming for Leetcode | Leetcode 3320 Count The Number of Winning Sequences • CF Step • 541 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Count The Number of Winning Sequences easy or hard?
Count The Number of Winning Sequences is classified as a Hard problem. The difficulty comes from modeling the cyclic win/lose rules, preventing consecutive moves, and tracking score differences across all rounds using dynamic programming.
Count The Number of Winning Sequences Python/Java solution
Python and Java implementations typically use dynamic programming or recursion with memoization. The state tracks the current index, the last move played by Bob, and the score difference relative to Alice. The algorithm iterates through possible moves while preventing consecutive duplicates and accumulates valid winning sequences.
How to solve Count The Number of Winning Sequences in O(n)?
An O(n) solution is generally not feasible because the score difference can vary across roughly 2n possible values at each step. The standard solution tracks these differences using dynamic programming, leading to O(n^2) time complexity. Attempts to compress the state still require iterating over possible score differences.
What is the best approach for Count The Number of Winning Sequences?
The most effective approach uses dynamic programming with state (index, lastMove, scoreDifference). For each round you try the three possible moves except the previous one and update the score difference depending on the game outcome. This reduces the search space to about O(n^2) states and efficiently counts all valid winning sequences.
Is Count The Number of Winning Sequences asked at Google/Amazon/Meta?
Hard dynamic programming problems involving game states and score differences are common in interviews at companies like Google, Amazon, and Meta. While this exact problem may not always appear, the pattern of modeling game outcomes with DP states is frequently tested.
What data structure is used in Count The Number of Winning Sequences?
The core data structure is a dynamic programming table or memoization cache storing states defined by index, last move, and score difference. Arrays or hash maps are commonly used depending on the language implementation.
What is the time complexity of Count The Number of Winning Sequences?
The optimal dynamic programming solution runs in O(n^2) time. The algorithm tracks states for each position, the previous move (3 possibilities), and the score difference ranging from about -n to +n. Space complexity is also O(n^2) due to the DP table storing these states.

Ready to solve this problem?

Practice Count The Number of Winning Sequences with our built-in code editor and test cases.

Practice on FleetCode
Previous

Predict the Winner