Count The Number of Winning Sequences

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 10^9 + 7.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10



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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11



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'.

Solution

Method 1 – Dynamic Programming with State Compression

Intuition

Bob must never repeat the same creature in consecutive rounds, and his goal is to strictly outscore Alice. We can use dynamic programming to count all valid Bob’s sequences, tracking the current round, the last creature Bob played, and the current score difference (Bob’s points minus Alice’s points). We use state compression to keep the DP feasible.

Approach

Map creatures to integers: F=0, W=1, E=2.
Define dp[i][last][diff]: number of ways for Bob to play from round i, last move ’last’, and score difference ‘diff’.
For each round, try all possible Bob’s moves (not repeating last), update the score difference according to the rules.
At the end, sum all ways where Bob’s score is strictly greater than Alice’s.
Use offset to handle negative score differences.
Use memoization to avoid recomputation.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


class Solution {
public:
    int countWinningSequences(string s) {
        const int MOD = 1e9+7;
        int n = s.size();
        vector<int> alice(n);
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'F') alice[i] = 0;
            else if (s[i] == 'W') alice[i] = 1;
            else alice[i] = 2;
        }
        vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(4, vector<int>(2*n+1, -1)));
        function<int(int,int,int)> dfs = [&](int i, int last, int diff) -> int {
            if (i == n) return diff > 0 ? 1 : 0;
            int &res = dp[i][last][diff+n];
            if (res != -1) return res;
            res = 0;
            for (int b = 0; b < 3; ++b) {
                if (b == last) continue;
                int d = 0;
                if ((b == 0 && alice[i] == 2) || (b == 1 && alice[i] == 0) || (b == 2 && alice[i] == 1)) d = 1;
                else if ((alice[i] == 0 && b == 2) || (alice[i] == 1 && b == 0) || (alice[i] == 2 && b == 1)) d = -1;
                res = (res + dfs(i+1, b, diff+d)) % MOD;
            }
            return res;
        };
        int ans = 0;
        for (int b = 0; b < 3; ++b) {
            ans = (ans + dfs(0, b, 0)) % MOD;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56


func countWinningSequences(s string) int {
    MOD := int(1e9 + 7)
    n := len(s)
    alice := make([]int, n)
    for i := 0; i < n; i++ {
        if s[i] == 'F' {
            alice[i] = 0
        } else if s[i] == 'W' {
            alice[i] = 1
        } else {
            alice[i] = 2
        }
    }
    dp := make([][][]int, n+1)
    for i := range dp {
        dp[i] = make([][]int, 4)
        for j := range dp[i] {
            dp[i][j] = make([]int, 2*n+1)
            for k := range dp[i][j] {
                dp[i][j][k] = -1
            }
        }
    }
    var dfs func(i, last, diff int) int
    dfs = func(i, last, diff int) int {
        if i == n {
            if diff > 0 {
                return 1
            }
            return 0
        }
        if dp[i][last][diff+n] != -1 {
            return dp[i][last][diff+n]
        }
        res := 0
        for b := 0; b < 3; b++ {
            if b == last {
                continue
            }
            d := 0
            if (b == 0 && alice[i] == 2) || (b == 1 && alice[i] == 0) || (b == 2 && alice[i] == 1) {
                d = 1
            } else if (alice[i] == 0 && b == 2) || (alice[i] == 1 && b == 0) || (alice[i] == 2 && b == 1) {
                d = -1
            }
            res = (res + dfs(i+1, b, diff+d)) % MOD
        }
        dp[i][last][diff+n] = res
        return res
    }
    ans := 0
    for b := 0; b < 3; b++ {
        ans = (ans + dfs(0, b, 0)) % MOD
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


class Solution {
    public int countWinningSequences(String s) {
        int MOD = 1_000_000_007;
        int n = s.length();
        int[] alice = new int[n];
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'F') alice[i] = 0;
            else if (s.charAt(i) == 'W') alice[i] = 1;
            else alice[i] = 2;
        }
        Integer[][][] dp = new Integer[n+1][4][2*n+1];
        java.util.function.BiFunction<Integer, Integer, Integer> dfs = new java.util.function.BiFunction<>() {
            public Integer apply(Integer i, Integer last) {
                throw new UnsupportedOperationException();
            }
        };
        java.util.function.Function<int[], Integer> rec = new java.util.function.Function<>() {
            public Integer apply(int[] state) {
                int i = state[0], last = state[1], diff = state[2];
                if (i == n) return diff > 0 ? 1 : 0;
                if (dp[i][last][diff+n] != null) return dp[i][last][diff+n];
                int res = 0;
                for (int b = 0; b < 3; b++) {
                    if (b == last) continue;
                    int d = 0;
                    if ((b == 0 && alice[i] == 2) || (b == 1 && alice[i] == 0) || (b == 2 && alice[i] == 1)) d = 1;
                    else if ((alice[i] == 0 && b == 2) || (alice[i] == 1 && b == 0) || (alice[i] == 2 && b == 1)) d = -1;
                    res = (res + this.apply(new int[]{i+1, b, diff+d})) % MOD;
                }
                return dp[i][last][diff+n] = res;
            }
        };
        int ans = 0;
        for (int b = 0; b < 3; b++) {
            ans = (ans + rec.apply(new int[]{0, b, 0})) % MOD;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
    fun countWinningSequences(s: String): Int {
        val MOD = 1_000_000_007
        val n = s.length
        val alice = IntArray(n) { when (s[it]) { 'F' -> 0; 'W' -> 1; else -> 2 } }
        val dp = Array(n+1) { Array(4) { IntArray(2*n+1) { -1 } } }
        fun dfs(i: Int, last: Int, diff: Int): Int {
            if (i == n) return if (diff > 0) 1 else 0
            if (dp[i][last][diff+n] != -1) return dp[i][last][diff+n]
            var res = 0
            for (b in 0..2) {
                if (b == last) continue
                var d = 0
                if ((b == 0 && alice[i] == 2) || (b == 1 && alice[i] == 0) || (b == 2 && alice[i] == 1)) d = 1
                else if ((alice[i] == 0 && b == 2) || (alice[i] == 1 && b == 0) || (alice[i] == 2 && b == 1)) d = -1
                res = (res + dfs(i+1, b, diff+d)) % MOD
            }
            dp[i][last][diff+n] = res
            return res
        }
        var ans = 0
        for (b in 0..2) {
            ans = (ans + dfs(0, b, 0)) % MOD
        }
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution:
    def countWinningSequences(self, s: str) -> int:
        MOD = 10**9 + 7
        n = len(s)
        alice = [0 if c == 'F' else 1 if c == 'W' else 2 for c in s]
        from functools import lru_cache
        @lru_cache(maxsize=None)
        def dfs(i: int, last: int, diff: int) -> int:
            if i == n:
                return 1 if diff > 0 else 0
            res = 0
            for b in range(3):
                if b == last:
                    continue
                d = 0
                if (b == 0 and alice[i] == 2) or (b == 1 and alice[i] == 0) or (b == 2 and alice[i] == 1):
                    d = 1
                elif (alice[i] == 0 and b == 2) or (alice[i] == 1 and b == 0) or (alice[i] == 2 and b == 1):
                    d = -1
                res = (res + dfs(i+1, b, diff+d)) % MOD
            return res
        ans = 0
        for b in range(3):
            ans = (ans + dfs(0, b, 0)) % MOD
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


impl Solution {
    pub fn count_winning_sequences(s: String) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let n = s.len();
        let alice: Vec<usize> = s.chars().map(|c| match c { 'F' => 0, 'W' => 1, _ => 2 }).collect();
        let mut dp = vec![vec![vec![-1; 2*n+1]; 4]; n+1];
        fn dfs(i: usize, last: usize, diff: i32, n: usize, alice: &Vec<usize>, dp: &mut Vec<Vec<Vec<i32>>>) -> i32 {
            if i == n { return if diff > 0 { 1 } else { 0 }; }
            if dp[i][last][(diff+n as i32) as usize] != -1 { return dp[i][last][(diff+n as i32) as usize]; }
            let mut res = 0;
            for b in 0..3 {
                if b == last { continue; }
                let mut d = 0;
                if (b == 0 && alice[i] == 2) || (b == 1 && alice[i] == 0) || (b == 2 && alice[i] == 1) { d = 1; }
                else if (alice[i] == 0 && b == 2) || (alice[i] == 1 && b == 0) || (alice[i] == 2 && b == 1) { d = -1; }
                res = (res + dfs(i+1, b, diff+d, n, alice, dp)) % MOD;
            }
            dp[i][last][(diff+n as i32) as usize] = res;
            res
        }
        let mut ans = 0;
        for b in 0..3 {
            ans = (ans + dfs(0, b, 0, n, &alice, &mut dp)) % MOD;
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
    countWinningSequences(s: string): number {
        const MOD = 1e9 + 7
        const n = s.length
        const alice = Array.from(s, c => c === 'F' ? 0 : c === 'W' ? 1 : 2)
        const dp = Array.from({length: n+1}, () => Array.from({length: 4}, () => Array(2*n+1).fill(-1)))
        function dfs(i: number, last: number, diff: number): number {
            if (i === n) return diff > 0 ? 1 : 0
            if (dp[i][last][diff+n] !== -1) return dp[i][last][diff+n]
            let res = 0
            for (let b = 0; b < 3; ++b) {
                if (b === last) continue
                let d = 0
                if ((b === 0 && alice[i] === 2) || (b === 1 && alice[i] === 0) || (b === 2 && alice[i] === 1)) d = 1
                else if ((alice[i] === 0 && b === 2) || (alice[i] === 1 && b === 0) || (alice[i] === 2 && b === 1)) d = -1
                res = (res + dfs(i+1, b, diff+d)) % MOD
            }
            dp[i][last][diff+n] = res
            return res
        }
        let ans = 0
        for (let b = 0; b < 3; ++b) {
            ans = (ans + dfs(0, b, 0)) % MOD
        }
        return ans
    }
}

Complexity

⏰ Time complexity: O(n^2 * 3) due to DP states (n rounds, 4 last moves, 2n+1 score differences).
🧺 Space complexity: O(n^2) for DP memoization.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Dynamic Programming with State Compression#

Intuition#

Approach#

Code#

Complexity#