#3320

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count The Number of Winning Sequences

Count The Number of Winning Sequences is a dynamic programming challenge involving state transitions based on Alice’s creature sequence.

string dynamic programming

Problem Statement

Alice and Bob are playing a fantasy battle game with n rounds, where each round, they summon one of three magical creatures: Fire Dragon (F), Water Serpent (W), or Earth Golem (E). Alice's sequence of moves is given as a string, s, where each character represents the creature Alice will summon in that round. Bob’s sequence of moves is unknown, but it is guaranteed that Bob will never summon the same creature in consecutive rounds.

The challenge is to determine the number of possible move sequences for Bob where the total points awarded to him exceed the points awarded to Alice after n rounds. A sequence is valid for Bob if he can beat Alice by having strictly more points. Use dynamic programming to find the total number of valid sequences Bob can have.

Examples

Example 1

Input: s = "FFF"

Output: 3

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

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 Approach

Dynamic Programming Setup

We define a 2D dynamic programming table, dp[i][j], where i represents the round number and j represents the last move made by Bob. For each round, we will calculate the number of ways Bob can make a valid move based on Alice’s current creature and the prior round's state.

State Transitions

State transitions depend on the previous round’s move by Bob. For example, if Bob’s last move was Fire Dragon, the next move can only be Water Serpent or Earth Golem. This ensures that Bob’s moves alternate and do not repeat consecutively. By tracking the transitions for all rounds, we can count valid sequences.

Counting Winning Sequences

After filling the dynamic programming table, sum the valid sequences where Bob’s points exceed Alice’s. This is done by comparing Bob’s potential total points against Alice’s fixed sequence.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the approach to state transitions and the number of rounds, but it can be reduced to O(n) where n is the length of Alice’s sequence. Space complexity can vary, but typically O(n) for storing the dynamic programming table and intermediate states.

What Interviewers Usually Probe

Does the candidate understand state transitions and dynamic programming?
Can the candidate break down a problem into subproblems using DP?
Is the candidate aware of how to optimize the space complexity of a DP approach?

Common Pitfalls or Variants

Common pitfalls

Not properly handling the state transitions between consecutive rounds for Bob.
Incorrectly counting the number of valid sequences or forgetting to compare Bob’s points against Alice’s.
Using an inefficient approach that results in a high time complexity, especially with larger input sizes.

Follow-up variants

What if the number of creatures is expanded to more than three types?
What if Bob is allowed to repeat moves in consecutive rounds?
What if the rounds are not fixed and are dynamically generated?

FAQ

What is the best dynamic programming approach for the Count The Number of Winning Sequences problem?

The optimal approach is to use dynamic programming with state transitions, where you track Bob’s possible valid sequences in each round and compare his total points with Alice’s.

How do state transitions work in the Count The Number of Winning Sequences problem?

State transitions ensure Bob alternates his moves, so after a Fire Dragon, Bob can only summon Water Serpent or Earth Golem in the next round. This keeps the sequences valid.

Can I optimize the space complexity of my dynamic programming solution for this problem?

Yes, space complexity can be optimized by using only two arrays to store the current and previous round’s valid sequences, reducing the need for a full 2D table.

How do I count the number of winning sequences?

After building the dynamic programming table, sum the sequences where Bob’s total points are strictly greater than Alice’s, considering the rules of the game.

What should I focus on when solving the Count The Number of Winning Sequences problem?

Focus on dynamic programming, state transitions, and ensuring you count only valid sequences where Bob beats Alice with a higher score.

terminal

Solution

Solution 1: Memoization Search

We design a function $\textit{dfs}(i, j, k)$, where $i$ represents starting from the $i$-th character of the string $s$, $j$ represents the current score difference between $\textit{Alice}$ and $\textit{Bob}$, and $k$ represents the last creature summoned by $\textit{Bob}$. The function calculates how many sequences of moves $\textit{Bob}$ can make to defeat $\textit{Alice}$.

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:
    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

Continue Practicing

#3316 find maximum removals from source string #3333 find the original typed string ii #3335 total characters in string after transformations i