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:
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:
s[i] == 'F', Alice summons a Fire Dragon.s[i] == 'W', Alice summons a Water Serpent.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:
"FWFWF", "FWFWE", "FWEFE", "FWEWE", "FEFWF", "FEFWE", "FEFEW", "FEWFE", "WFEFE", "WFEWE", "WEFWF", "WEFWE", "WEFEF", "WEFEW", "WEWFW", "WEWFE", "EWFWE", or "EWEWE".
Constraints:
1 <= s.length <= 1000s[i] is one of 'F', 'W', or 'E'.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.
The fundamental observation is that Bob will summon sequences with the following constraints:
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 result is computed by summing up all possible ways Bob can arrange his creatures to have more points than Alice.
Python
JavaScript
Time Complexity: O(n) where n is the length of string s.
Space Complexity: O(n) due to the size of the DP table.
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.
Time Complexity: O(n * 3^2) where n is the length of string s.
Space Complexity: O(n * 3 * 2) for memo storage.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: |
| Recursive Backtracking with Memoization | Time Complexity: |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking with Memoization | O(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. |
Dynamic Programming for Leetcode | Leetcode 3320 Count The Number of Winning Sequences • CF Step • 502 views views
Watch 8 more video solutions →Practice Count The Number of Winning Sequences with our built-in code editor and test cases.
Practice on FleetCode