Count The Number of Winning Sequences
HardPrompt
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:
"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'.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the problem into a recursive structure. We explore every possible valid sequence of moves for Bob. A sequence is valid if Bob does not make the same move in two consecutive rounds. For each complete valid sequence, we check if Bob's final score is strictly greater than Alice's. We count all such sequences.
Algorithm
- Define a recursive function, say
countSequences(round, prev_bob_move, score_diff), which will count the winning sequences from the currentround. - The parameters are:
round: The current round index (from 0 to n-1).prev_bob_move: The creature Bob summoned in the previous round, to enforce the constraint that Bob cannot play the same move twice.score_diff: The accumulated score difference (Bob's score - Alice's score).
- Base Case: If
round == n, all rounds have been played. Ifscore_diff > 0, it means Bob won, so we return 1. Otherwise, we return 0. - Recursive Step: For the current
round, iterate through all three possible moves for Bob ('F', 'W', 'E'). - For each potential move, check if it's the same as
prev_bob_move. If it is, skip this move. - If the move is valid, calculate the score change for the current round based on Alice's move
s[round]and Bob's potential move. - Make a recursive call for the next round:
countSequences(round + 1, current_bob_move, score_diff + score_change). - Sum the results from all valid recursive calls. This sum is the result for the current state.
- The initial call would be
countSequences(0, null, 0).
Walkthrough
We can define a recursive function that explores the decision tree of Bob's possible moves. The state of our recursion at any point is determined by the current round, Bob's previous move, and the score difference accumulated so far. The function will branch out for each valid move Bob can make in the current round. The recursion bottoms out when all n rounds are completed, at which point we check the final score difference to see if it constitutes a win for Bob.
class Solution { private int n; private String s; private final int MOD = 1_000_000_007; public int countWinningSequences(String s) { this.n = s.length(); this.s = s; // The initial call has no previous move (' ') and a score difference of 0. return (int) solve(0, ' ', 0); } private long solve(int index, char prevBobMove, int scoreDiff) { // Base case: all rounds are over if (index == n) { return scoreDiff > 0 ? 1 : 0; } long count = 0; char aliceMove = s.charAt(index); char[] bobMoves = {'F', 'W', 'E'}; // Explore all possible moves for Bob in the current round for (char bobMove : bobMoves) { // Bob cannot repeat his move if (bobMove == prevBobMove) { continue; } int currentRoundScoreChange = calculateScore(bobMove, aliceMove); count = (count + solve(index + 1, bobMove, scoreDiff + currentRoundScoreChange)) % MOD; } return count; } private int calculateScore(char bob, char alice) { if (bob == alice) return 0; if ((bob == 'F' && alice == 'E') || (bob == 'W' && alice == 'F') || (bob == 'E' && alice == 'W')) { return 1; // Bob wins } return -1; // Alice wins }}Complexity
Time
O(3 * 2^(n-1)) or simply O(2^n). For each round, Bob has at most 2 choices (after the first round where he has 3). This creates an exponential number of paths to explore.
Space
O(n), for the depth of the recursion stack.
Trade-offs
Pros
Simple to conceptualize and implement.
Follows the problem description in a straightforward manner.
Cons
Extremely inefficient due to its exponential time complexity.
It recomputes the same subproblems multiple times, leading to a Time Limit Exceeded (TLE) error on larger inputs.
The brute-force recursion is inefficient because it repeatedly solves the same subproblems. For instance, the number of ways to win from round i with a certain score difference and previous move is calculated multiple times through different paths. We can optimize this by using memoization, a technique where we store the results of expensive function calls and return the cached result when the same inputs occur again. This is a top-down dynamic programming approach.
Algorithm
- Use the same recursive structure as the brute-force approach.
- Introduce a memoization table,
memo[index][prev_move_code][score_diff_offset], to store the results of subproblems. - The state is defined by
(index, prev_move_code, score_diff).index: current round,0ton-1.prev_move_code: an integer representing Bob's last move (e.g., 0 for 'F', 1 for 'W', 2 for 'E', and 3 for the initial state with no previous move).score_diff: the score difference. Since it can be negative, we use an offset (e.g.,score_diff + n) to map it to a non-negative array index.
- In the recursive function, before any computation, check if the result for the current state
(index, prev_move_code, score_diff)is already in the memo table. If yes, return the stored value. - If not, compute the result as in the brute-force approach.
- Before returning, store the computed result in the memo table.
Walkthrough
We augment the recursive solution with a 3D array to cache results. The dimensions of this array correspond to the parameters that define a unique subproblem: the current round index, Bob's previous move, and the current score difference. By storing and retrieving results from this cache, we ensure that each unique subproblem is solved only once.
class Solution { private int n; private int[] aliceMoves; private long[][][] memo; private final int MOD = 1_000_000_007; public int countWinningSequences(String s) { this.n = s.length(); this.aliceMoves = new int[n]; for (int i = 0; i < n; i++) { char c = s.charAt(i); if (c == 'F') aliceMoves[i] = 0; else if (c == 'W') aliceMoves[i] = 1; else aliceMoves[i] = 2; } // memo[index][prev_move_code][score_diff + n] // prev_move_code: 0=F, 1=W, 2=E, 3=None this.memo = new long[n][4][2 * n + 1]; for (long[][] plane : memo) { for (long[] row : plane) { java.util.Arrays.fill(row, -1); } } return (int) solve(0, 3, 0); } private long solve(int index, int prevBobMove, int scoreDiff) { if (index == n) { return scoreDiff > 0 ? 1 : 0; } if (memo[index][prevBobMove][scoreDiff + n] != -1) { return memo[index][prevBobMove][scoreDiff + n]; } long ans = 0; int aliceMove = aliceMoves[index]; for (int bobMove = 0; bobMove < 3; bobMove++) { if (bobMove == prevBobMove) { continue; } int scoreChange = calculateScore(bobMove, aliceMove); ans = (ans + solve(index + 1, bobMove, scoreDiff + scoreChange)) % MOD; } return memo[index][prevBobMove][scoreDiff + n] = ans; } private int calculateScore(int bob, int alice) { if (bob == alice) return 0; // F=0, W=1, E=2. Bob wins if bob == (alice+1)%3, but that's not the rule. // Rule: W>F, E>W, F>E if ((bob == 0 && alice == 2) || (bob == 1 && alice == 0) || (bob == 2 && alice == 1)) { return 1; // Bob wins } return -1; // Alice wins }}Complexity
Time
O(n^2). The number of states is `n * 4 * (2n+1)`. Each state is computed once, and the computation inside takes constant time (a loop of size 3).
Space
O(n^2), for the memoization table of size `n * 4 * (2n+1)`.
Trade-offs
Pros
Drastically improves time complexity from exponential to polynomial.
Guarantees that each subproblem is solved only once.
It's often more intuitive to write than the bottom-up iterative version.
Cons
The space complexity is O(n^2), which might be large for memory-constrained environments, although it's acceptable for the given constraints.
This approach is the iterative, or bottom-up, version of the dynamic programming solution. Instead of starting from the final goal and breaking it down (top-down), we start from the base case (the first round) and build our way up to the solution for n rounds. This approach often allows for space optimizations. Since the calculation for round i only depends on the results of round i-1, we don't need to store the entire history of DP states, reducing space complexity.
Algorithm
- Define a 2D DP table,
dp[diff_offset][last_move], to store the number of ways to end a round with a certain score difference and last move. We only need to keep track of the previous round's results to compute the current one. - Initialize a
dptable representing the state after the first round. For each of Bob's 3 possible moves, calculate the score differencedand setdp[n+d][move] = 1. - Iterate from the second round (
i = 1) to the last round (n-1). In each iteration, we compute anext_dptable based on the currentdptable. - To optimize the transition, first calculate an auxiliary array
total_prev[diff_offset]which sums up the ways for each score difference in the previous round:dp[diff_offset][0] + dp[diff_offset][1] + dp[diff_offset][2]. - For each
current_moveandprev_diff, the number of ways to transition istotal_prev[prev_diff_offset] - dp[prev_diff_offset][current_move](sincecurrent_movecannot equalprev_move). - Add this number to
next_dp[prev_diff_offset + score_change][current_move]. - After the inner loops, replace
dpwithnext_dp. - After iterating through all
nrounds, sum up the values in the finaldptable for all winning score differences (i.e.,diff > 0).
Walkthrough
We use a 2D array, dp[score_diff + n][last_move], to store the number of sequences. We iterate from round 1 to n. In each round i, we compute the next_dp states based on the dp states from round i-1. The key insight for an efficient transition is that for a current_move, the previous move can be any of the other two moves. So, the number of ways to arrive at the current state is the sum of all ways from the previous round that ended in a different move. We can find this by taking the total ways for a given score difference in the previous round and subtracting the ways that ended with the same move we are considering now. This avoids an extra loop over previous moves.
class Solution { public int countWinningSequences(String s) { int n = s.length(); int MOD = 1_000_000_007; int[] aliceMoves = new int[n]; for (int i = 0; i < n; i++) { char c = s.charAt(i); if (c == 'F') aliceMoves[i] = 0; else if (c == 'W') aliceMoves[i] = 1; else aliceMoves[i] = 2; } // dp[diff + n][last_move] long[][] dp = new long[2 * n + 1][3]; // Base case: i = 0 (first round) for (int bobMove = 0; bobMove < 3; bobMove++) { int scoreChange = calculateScore(bobMove, aliceMoves[0]); dp[n + scoreChange][bobMove] = 1; } // Transition: i = 1 to n-1 for (int i = 1; i < n; i++) { long[][] next_dp = new long[2 * n + 1][3]; long[] totalPrev = new long[2 * n + 1]; // The score difference after i rounds (0-indexed) is in [-i, i] for (int diff = -i; diff <= i; diff++) { int diffIdx = n + diff; totalPrev[diffIdx] = (dp[diffIdx][0] + dp[diffIdx][1] + dp[diffIdx][2]) % MOD; } for (int bobMove = 0; bobMove < 3; bobMove++) { int scoreChange = calculateScore(bobMove, aliceMoves[i]); for (int prevDiff = -i; prevDiff <= i; prevDiff++) { int prevDiffIdx = n + prevDiff; if (totalPrev[prevDiffIdx] == 0) continue; long waysFromPrev = (totalPrev[prevDiffIdx] - dp[prevDiffIdx][bobMove] + MOD) % MOD; if (waysFromPrev > 0) { int nextDiffIdx = prevDiffIdx + scoreChange; next_dp[nextDiffIdx][bobMove] = (next_dp[nextDiffIdx][bobMove] + waysFromPrev) % MOD; } } } dp = next_dp; } // Final result: sum ways for all winning scores (diff > 0) long ans = 0; for (int diff = 1; diff <= n; diff++) { int diffIdx = n + diff; ans = (ans + dp[diffIdx][0]) % MOD; ans = (ans + dp[diffIdx][1]) % MOD; ans = (ans + dp[diffIdx][2]) % MOD; } return (int) ans; } private int calculateScore(int bob, int alice) { if (bob == alice) return 0; if ((bob == 0 && alice == 2) || (bob == 1 && alice == 0) || (bob == 2 && alice == 1)) { return 1; // Bob wins } return -1; // Alice wins }}Complexity
Time
O(n^2). The main loop runs `n` times. Inside, we iterate through `O(n)` possible differences and 3 moves.
Space
O(n). We use two 2D arrays of size `(2n+1) x 3`, which simplifies to O(n).
Trade-offs
Pros
Highly efficient in both time and space.
Avoids recursion overhead, which can be faster in practice.
The space optimization makes it suitable for very large
nwhere O(n^2) space might be an issue.
Cons
The logic can be less intuitive to formulate compared to the top-down recursive approach.
Requires careful management of DP states and indices.
Solutions
Solution
class Solution {private int n;private char[] s;private int[] d = new int[26];private Integer[][][] f;private final int mod = (int)1 e9 + 7;public int countWinningSequences(String s) { d['W' - 'A'] = 1; d['E' - 'A'] = 2; this.s = s.toCharArray(); n = this.s.length; f = new Integer[n][n + n + 1][4]; return dfs(0, n, 3); }private int dfs(int i, int j, int k) { if (n - i <= j - n) { return 0; } if (i >= n) { return j - n < 0 ? 1 : 0; } if (f[i][j][k] != null) { return f[i][j][k]; } int ans = 0; for (int l = 0; l < 3; ++l) { if (l == k) { continue; } ans = (ans + dfs(i + 1, j + calc(d[s[i] - 'A'], l), l)) % mod; } return f[i][j][k] = ans; }private int calc(int x, int y) { if (x == y) { return 0; } if (x < y) { return x == 0 && y == 2 ? 1 : -1; } return x == 2 && y == 0 ? -1 : 1; }}class Solution {public: int countWinningSequences(string s) { int n = s.size(); int d[26]{}; d['W' - 'A'] = 1; d['E' - 'A'] = 2; int f[n][n + n + 1][4]; memset(f, -1, sizeof(f)); auto calc = [](int x, int y) -> int { if (x == y) { return 0; } if (x < y) { return x == 0 && y == 2 ? 1 : -1; } return x == 2 && y == 0 ? -1 : 1; }; const int mod = 1e9 + 7; auto dfs = [&](auto &&dfs, int i, int j, int k) -> int { if (n - i <= j - n) { return 0; } if (i >= n) { return j - n < 0 ? 1 : 0; } if (f[i][j][k] != -1) { return f[i][j][k]; } int ans = 0; for (int l = 0; l < 3; ++l) { if (l == k) { continue; } ans = (ans + dfs(dfs, i + 1, j + calc(d[s[i] - 'A'], l), l)) % mod; } return f[i][j][k] = ans; }; return dfs(dfs, 0, n, 3); }};class Solution: def countWinningSequences(self, s: str) -> int: def calc(x: int, y: int) -> int: if x == y: return 0 if x < y: return 1 if x == 0 and y == 2 else - 1 return - 1 if x == 2 and y == 0 else 1 @ cache def dfs(i: int, j: int, k: int) -> int: if len(s) - i <= j: return 0 if i >= len(s): return int(j < 0) res = 0 for l in range(3): if l == k: continue res = (res + dfs(i + 1, j + calc(d[s[i]], l), l)) % mod return res mod = 10 ** 9 + 7 d = {"F": 0, "W": 1, "E": 2} ans = dfs(0, 0, - 1) dfs . cache_clear() return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.