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'.In #3320 Count The Number of Winning Sequences, you must count how many sequences of moves lead to a final score where the player wins against the opponent’s predefined move string. Each move interacts with the opponent’s move using a cyclic win/lose relationship, making the outcome dependent on both the current choice and previous decisions.
A practical strategy is to use dynamic programming. Track the state using the current index in the string, the score difference between players, and the last move chosen to enforce the rule that the same move cannot be repeated consecutively. For each position, try all valid moves and update the score difference depending on whether the move wins, loses, or ties against the opponent’s move.
To keep the state manageable, store results using a DP table or memoization with an offset for score differences. The total number of winning sequences is obtained by summing states where the final score difference is positive. This approach runs in roughly O(n * range * 3) time with manageable memory using optimized DP transitions.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with score difference and last move state | O(n * d * 3) | O(n * d * 3) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Use dynamic programming.
For <code>0 < i < n - 1</code>, <code>-n < j < n</code>, and <code>k</code> in <code>{’F’, ‘W’, ‘E’}</code>, let <code>dp[i][j][k]</code> be the number of sequences consisting of the first <code>i</code> moves such that the difference between bob’s points and alice’s point is equal to <code>j</code> and the <code>i<sup>th</sup></code> move that Bob played is <code>k</code>.
The answer is the sum of <code>dp[n - 1][j][k]</code>over all <code>j > 0</code> and over all <code>k</code>.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Hard dynamic programming problems like this often appear in advanced coding interviews at top tech companies. While the exact problem may vary, similar DP state-transition and game simulation questions are common in FAANG-style interviews.
The optimal approach uses dynamic programming. Track the index in the string, the current score difference, and the last move taken to avoid consecutive repeats. By exploring all valid transitions and counting only states where the final score difference is positive, you can compute the number of winning sequences efficiently.
A DP table or memoization map is typically used to store states defined by index, score difference, and last move. Arrays or hash-based memoization structures help efficiently retrieve previously computed results.
Dynamic programming works well because the result at each step depends on previous decisions such as the last move and current score difference. By storing intermediate results, DP avoids recomputation and efficiently explores all valid move combinations.