LeetCode 3320 - Count The Number of Winning Sequences

We are given a string s representing Alice’s moves across n rounds of a game. Each character corresponds to one creature: - 'F' = Fire Dragon - 'W' = Water Serpent - 'E' = Earth Golem In every round, Alice and Bob each choose one creature simultaneously.

leetcodehardstringdynamic-programming

LeetCode Problem 3320

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming

Solution

Problem Understanding

We are given a string s representing Alice’s moves across n rounds of a game. Each character corresponds to one creature:

  • 'F' = Fire Dragon
  • 'W' = Water Serpent
  • 'E' = Earth Golem

In every round, Alice and Bob each choose one creature simultaneously. Depending on the matchup, exactly one player may gain a point:

  • Fire beats Earth
  • Water beats Fire
  • Earth beats Water
  • Same creature results in no points

This is essentially a cyclic rock-paper-scissors style game.

The important detail is that Bob’s sequence is not known in advance, and we must count how many valid sequences Bob can choose such that:

  1. Bob never uses the same creature in two consecutive rounds.
  2. Bob’s final score is strictly greater than Alice’s score.

The result must be returned modulo:

$10^9 + 7$

The constraints are important:

  • 1 <= n <= 1000

A brute-force search would require trying nearly all sequences of length n over three choices with adjacency restrictions. That is exponential and completely infeasible for n = 1000.

The scoring system also matters carefully. Each round contributes one of three outcomes:

  • Bob wins the round: +1
  • Alice wins the round: -1
  • Draw: 0

Instead of tracking both players' scores separately, we only need the score difference:

$\text{difference} = \text{BobScore} - \text{AliceScore}$

At the end, Bob wins if:

$\text{difference} > 0$

Several edge cases are important:

  • A single round, where Bob must simply choose a winning creature.
  • Strings where Alice repeats the same move many times, because Bob still cannot repeat consecutive moves.
  • Situations where Bob is temporarily losing but can recover later, meaning greedy choices do not work.
  • Large inputs of length 1000, which require polynomial time dynamic programming.

Approaches

Brute Force

The brute-force solution generates every valid sequence Bob can play.

At each round, Bob has at most three choices, except he cannot repeat the previous move. Therefore, after the first move, each round has at most two choices.

For every generated sequence:

  1. Simulate all rounds.
  2. Compute the final score difference.
  3. Count the sequence if Bob wins.

This approach is correct because it explicitly enumerates every legal sequence and checks the game outcome exactly.

However, the number of sequences grows exponentially. The first round has 3 choices, and each later round has about 2 choices:

$3 \cdot 2^{n-1}$

For n = 1000, this is astronomically large and impossible to compute.

Optimal Dynamic Programming

The key observation is that the game state only depends on:

  1. The current round index
  2. Bob’s previous move
  3. The current score difference

We do not need to remember the entire history.

This naturally leads to dynamic programming.

For every round, we try all valid next moves for Bob. Each move changes the score difference by -1, 0, or +1.

The number of possible score differences after n rounds is bounded by:

$[-n, n]$

Thus the total number of states is manageable:

$O(n \times 3 \times 2n)$

This fits comfortably within the constraints.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force $O(2^n)$ $O(n)$ Enumerates all valid Bob sequences
Optimal Dynamic Programming $O(n^2)$ $O(n^2)$ Tracks round index, previous move, and score difference

Algorithm Walkthrough

Step 1: Encode the creatures

We map the creatures to integers for easier processing:

  • F -> 0
  • W -> 1
  • E -> 2

This makes transition logic simpler.

Step 2: Define the round outcome function

We create a helper function that returns:

  • +1 if Bob wins the round
  • -1 if Alice wins the round
  • 0 for a draw

The cyclic winning rule is:

  • Fire beats Earth
  • Water beats Fire
  • Earth beats Water

A compact way to determine this is:

  • Bob wins if (bob - alice) % 3 == 1
  • Alice wins if (alice - bob) % 3 == 1
  • Otherwise draw

Step 3: Define the DP state

We define:

dp[i][prev][diff]

Meaning:

  • We have processed the first i rounds
  • Bob’s previous move is prev
  • Current score difference is diff

The value stored is the number of ways to reach this state.

Because diff can be negative, we use an offset:

shift = n

So actual array index becomes:

diff + shift

Step 4: Initialize the first round

For round 0, Bob may choose any creature.

For each possible move:

  1. Compute the round result
  2. Store one valid way in the DP table

Step 5: Transition between rounds

For every state:

  1. Try all three possible next moves
  2. Skip moves equal to the previous move
  3. Compute the new score difference
  4. Add the count into the next DP state

This explores all valid Bob sequences while respecting the adjacency rule.

Step 6: Count winning final states

After processing all rounds, sum every state whose final score difference is positive.

That gives the number of winning sequences.

Why it works

The DP state captures all information needed to continue the game optimally:

  • The current round determines which Alice move is next.
  • The previous Bob move determines which moves are legal.
  • The score difference determines whether Bob is currently ahead or behind.

Since every valid transition is explored exactly once, and every illegal transition is excluded, the DP counts all valid winning sequences exactly once.

Python Solution

class Solution:
    def countWinningSequences(self, s: str) -> int:
        MOD = 10**9 + 7
        n = len(s)

        mapping = {
            'F': 0,
            'W': 1,
            'E': 2
        }

        alice = [mapping[c] for c in s]

        def outcome(bob: int, alice_move: int) -> int:
            if bob == alice_move:
                return 0

            if (bob - alice_move) % 3 == 1:
                return 1

            return -1

        offset = n

        dp = [[[0] * (2 * n + 1) for _ in range(3)] for _ in range(n)]

        for first_move in range(3):
            diff = outcome(first_move, alice[0])
            dp[0][first_move][diff + offset] = 1

        for i in range(1, n):
            for prev_move in range(3):
                for diff_index in range(2 * n + 1):
                    current_count = dp[i - 1][prev_move][diff_index]

                    if current_count == 0:
                        continue

                    current_diff = diff_index - offset

                    for next_move in range(3):
                        if next_move == prev_move:
                            continue

                        round_result = outcome(next_move, alice[i])
                        new_diff = current_diff + round_result

                        dp[i][next_move][new_diff + offset] += current_count
                        dp[i][next_move][new_diff + offset] %= MOD

        answer = 0

        for last_move in range(3):
            for diff in range(1, n + 1):
                answer += dp[n - 1][last_move][diff + offset]
                answer %= MOD

        return answer

The implementation begins by converting Alice’s characters into numeric values. This avoids repeated string comparisons during transitions.

The outcome() helper computes the score contribution for a single round. It returns +1, 0, or -1.

The DP table stores the number of ways to reach each state. Since score differences can be negative, an offset shifts them into valid array indices.

Initialization handles the first round separately because there is no previous move restriction yet.

The main transition loop processes each round. For every reachable state, the algorithm tries every legal next move for Bob. Illegal repeated moves are skipped.

Finally, after all rounds are processed, the algorithm sums every state where the score difference is positive.

Go Solution

func countWinningSequences(s string) int {
	const MOD int = 1_000_000_007

	n := len(s)

	mapping := map[byte]int{
		'F': 0,
		'W': 1,
		'E': 2,
	}

	alice := make([]int, n)

	for i := 0; i < n; i++ {
		alice[i] = mapping[s[i]]
	}

	outcome := func(bob int, aliceMove int) int {
		if bob == aliceMove {
			return 0
		}

		if (bob-aliceMove+3)%3 == 1 {
			return 1
		}

		return -1
	}

	offset := n

	dp := make([][][]int, n)

	for i := 0; i < n; i++ {
		dp[i] = make([][]int, 3)

		for j := 0; j < 3; j++ {
			dp[i][j] = make([]int, 2*n+1)
		}
	}

	for firstMove := 0; firstMove < 3; firstMove++ {
		diff := outcome(firstMove, alice[0])
		dp[0][firstMove][diff+offset] = 1
	}

	for i := 1; i < n; i++ {
		for prevMove := 0; prevMove < 3; prevMove++ {
			for diffIndex := 0; diffIndex <= 2*n; diffIndex++ {
				currentCount := dp[i-1][prevMove][diffIndex]

				if currentCount == 0 {
					continue
				}

				currentDiff := diffIndex - offset

				for nextMove := 0; nextMove < 3; nextMove++ {
					if nextMove == prevMove {
						continue
					}

					roundResult := outcome(nextMove, alice[i])
					newDiff := currentDiff + roundResult

					dp[i][nextMove][newDiff+offset] += currentCount
					dp[i][nextMove][newDiff+offset] %= MOD
				}
			}
		}
	}

	answer := 0

	for lastMove := 0; lastMove < 3; lastMove++ {
		for diff := 1; diff <= n; diff++ {
			answer += dp[n-1][lastMove][diff+offset]
			answer %= MOD
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python version. The primary differences are related to language structure and memory management.

Go requires explicit multidimensional slice allocation. Integer modulo handling also requires care because % can produce negative values, so the expression:

(bob - aliceMove + 3) % 3

ensures non-negative results.

The rest of the algorithm remains identical.

Worked Examples

Example 1

Input:

s = "FFF"

Alice always plays Fire.

Round outcomes

Bob Move Result
F 0
W +1
E -1

Initial states

Bob Move Diff Ways
F 0 1
W 1 1
E -1 1

After Round 2

From previous states, Bob cannot repeat moves.

Previous Next New Diff
F(0) W 1
F(0) E -1
W(1) F 1
W(1) E 0
E(-1) F -1
E(-1) W 0

After Round 3

Continuing transitions gives final positive-difference sequences:

WFW
FWF
WEW

Answer:

3

Example 2

Input:

s = "FWEFW"

The DP explores all legal non-repeating Bob sequences while maintaining score differences.

At every round:

  • Legal moves depend on previous move
  • Score difference changes by -1, 0, or +1

The DP accumulates counts of all reachable states.

Final count of positive-difference states:

18

Complexity Analysis

Measure Complexity Explanation
Time $O(n^2)$ There are O(n * 3 * 2n) states and constant transitions
Space $O(n^2)$ DP table stores all score-difference states

The score difference ranges from -n to +n, giving 2n + 1 possibilities. For every round and previous move, we process all reachable score differences and try at most three next moves.

This leads to quadratic complexity, which is efficient enough for n <= 1000.

Test Cases

sol = Solution()

assert sol.countWinningSequences("F") == 1
# Single round, Bob can only win by playing W

assert sol.countWinningSequences("W") == 1
# Single round, Bob can only win by playing E

assert sol.countWinningSequences("E") == 1
# Single round, Bob can only win by playing F

assert sol.countWinningSequences("FFF") == 3
# Provided example

assert sol.countWinningSequences("FWEFW") == 18
# Provided example

assert sol.countWinningSequences("FW") > 0
# Small mixed input

assert sol.countWinningSequences("FE") > 0
# Another small mixed input

assert sol.countWinningSequences("WWWW") > 0
# Repeated Alice moves with Bob adjacency restriction

assert sol.countWinningSequences("FWEFWE") > 0
# Alternating pattern

assert sol.countWinningSequences("EEEEEE") > 0
# Uniform Alice sequence

long_input = "FWE" * 300 + "F"
assert sol.countWinningSequences(long_input) >= 0
# Stress test near maximum length

Test Summary

Test Why
"F" Smallest possible input
"W" Single-round Water case
"E" Single-round Earth case
"FFF" Provided example
"FWEFW" Larger provided example
"FW" Small mixed pattern
"FE" Validates transitions
"WWWW" Repeated Alice move pattern
"FWEFWE" Alternating sequence
"EEEEEE" Uniform Earth sequence
Long repeated input Performance stress test

Edge Cases

One important edge case is a single-round game. In this situation, Bob only has one move to make, and the adjacency restriction is irrelevant because there is no previous move. A buggy implementation might incorrectly apply the no-repeat rule even on the first move. The implementation handles this cleanly by initializing the first round separately before entering the transition loop.

Another important case is when Alice repeats the same move many times, such as "FFFFF". Bob may want to repeatedly play the winning counter move, but the problem forbids consecutive identical moves. A greedy solution that always picks the winning move would generate illegal sequences. The DP explicitly tracks the previous move and skips invalid transitions.

A third tricky case is when Bob temporarily falls behind before recovering later. For example, some optimal sequences may require taking an early loss to enable stronger future transitions. Any greedy or locally optimal strategy would fail here. The DP correctly explores all valid sequences and preserves every reachable score difference state.

A final edge case involves negative score differences. Since array indices cannot be negative, implementations that directly index by score difference would fail. The solution uses an offset of n, mapping the range [-n, n] into [0, 2n], ensuring all states are stored safely.