Watch 9 video solutions for Count The Number of Winning Sequences, a hard level problem involving String, Dynamic Programming. This walkthrough by CF Step has 502 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |