# Count The Number of Winning Sequences
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-the-number-of-winning-sequences)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-winning-sequences
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
---
## Problem
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'`.

# Approaches
## Brute-Force Recursion
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.
**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.
**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.
### Explanation
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.

```java
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
    }
}
```
### Algorithm
1. Define a recursive function, say `countSequences(round, prev_bob_move, score_diff)`, which will count the winning sequences from the current `round`.
2. 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).
3. **Base Case:** If `round == n`, all rounds have been played. If `score_diff > 0`, it means Bob won, so we return 1. Otherwise, we return 0.
4. **Recursive Step:** For the current `round`, iterate through all three possible moves for Bob ('F', 'W', 'E').
5. For each potential move, check if it's the same as `prev_bob_move`. If it is, skip this move.
6. 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.
7. Make a recursive call for the next round: `countSequences(round + 1, current_bob_move, score_diff + score_change)`.
8. Sum the results from all valid recursive calls. This sum is the result for the current state.
9. The initial call would be `countSequences(0, null, 0)`.

## Top-Down Dynamic Programming (Memoization)
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.
**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)`.
**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.
### Explanation
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.

```java
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
    }
}
```
### Algorithm
1. Use the same recursive structure as the brute-force approach.
2. Introduce a memoization table, `memo[index][prev_move_code][score_diff_offset]`, to store the results of subproblems.
3. The state is defined by `(index, prev_move_code, score_diff)`.
    - `index`: current round, `0` to `n-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.
4. 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.
5. If not, compute the result as in the brute-force approach.
6. Before returning, store the computed result in the memo table.

## Bottom-Up Dynamic Programming with Space Optimization
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.
**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).
**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 `n` where 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.
### Explanation
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.

```java
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
    }
}
```
### Algorithm
1. 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.
2. Initialize a `dp` table representing the state after the first round. For each of Bob's 3 possible moves, calculate the score difference `d` and set `dp[n+d][move] = 1`.
3. Iterate from the second round (`i = 1`) to the last round (`n-1`). In each iteration, we compute a `next_dp` table based on the current `dp` table.
4. 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]`.
5. For each `current_move` and `prev_diff`, the number of ways to transition is `total_prev[prev_diff_offset] - dp[prev_diff_offset][current_move]` (since `current_move` cannot equal `prev_move`).
6. Add this number to `next_dp[prev_diff_offset + score_change][current_move]`.
7. After the inner loops, replace `dp` with `next_dp`.
8. After iterating through all `n` rounds, sum up the values in the final `dp` table for all winning score differences (i.e., `diff > 0`).

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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);
  }
};

```

### Python

```python
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 ans

```