Facebook Pixel

3320. Count The Number of Winning Sequences

HardStringDynamic Programming
Leetcode Link

Problem Description

This is a game theory problem where Alice and Bob play a fantasy battle game for n rounds. In each round, both players simultaneously summon one of three magical creatures:

  • Fire Dragon (F)
  • Water Serpent (W)
  • Earth Golem (E)

The scoring rules follow a rock-paper-scissors pattern:

  • Fire Dragon beats Earth Golem (Fire Dragon player gets 1 point)
  • Water Serpent beats Fire Dragon (Water Serpent player gets 1 point)
  • Earth Golem beats Water Serpent (Earth Golem player gets 1 point)
  • If both players summon the same creature, no points are awarded

You're given a string s of length n containing characters 'F', 'W', and 'E', representing Alice's predetermined sequence of creatures for each round.

Bob's strategy has one constraint: he cannot summon the same creature in two consecutive rounds. Bob wins if his total points are strictly greater than Alice's points after all n rounds.

The task is to count how many distinct valid sequences Bob can use to beat Alice. Since this number can be very large, return the result modulo 10^9 + 7.

For example, if Alice's sequence is "FWE", Bob needs to find sequences where:

  1. He doesn't repeat creatures consecutively
  2. His total score against Alice's sequence is positive (Bob's points > Alice's points)

The solution uses dynamic programming with memoization, tracking:

  • Current round position
  • Score difference (Alice's score minus Bob's score)
  • Bob's last summoned creature (to enforce the no-consecutive-repeat rule)

The function explores all valid sequences Bob can play and counts those where he ends with more points than Alice.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is that we need to count all possible sequences Bob can play that result in him winning. Since Bob's choices depend on what he played previously (no consecutive repeats), this suggests a dynamic programming approach where we track the game state.

Think about what information we need to determine if Bob can win from any given position:

  1. Current round (i): We need to know which round we're in to access Alice's move from string s
  2. Score difference (j): We need to track the running score to know if Bob is winning
  3. Bob's last move (k): We need this to ensure Bob doesn't repeat creatures consecutively

For each state, we can try all three possible creatures Bob could summon (F, W, E), but skip any that match his previous move. Each choice leads to a new state with updated score difference.

The scoring can be viewed as a circular relationship: F → E → W → F, where each creature beats the next one in the cycle. We can encode this as numbers (F=0, W=1, E=2) and create a scoring function calc(x, y) that returns:

  • 1 if x beats y
  • -1 if y beats x
  • 0 if it's a tie

An important optimization comes from recognizing when Bob can no longer win: if the remaining rounds (n - i) are less than or equal to the current score deficit j (where j represents Alice's lead), Bob cannot catch up even if he wins every remaining round. This allows us to prune the search tree early.

The memoization helps avoid recalculating the same game states multiple times. Starting from round 0 with score difference 0 and no previous move for Bob (represented as -1), we recursively explore all valid sequences and count those where Bob ends with a negative score difference (meaning Bob has more points than Alice).

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses memoization search (dynamic programming with recursion) to count all valid sequences where Bob beats Alice.

Data Structures:

  • Dictionary d = {"F": 0, "W": 1, "E": 2} maps characters to numbers for easier calculation
  • @cache decorator for memoization to store already computed states

Helper Function: The calc(x, y) function determines the scoring outcome between creatures x and y:

  • If x == y: return 0 (tie)
  • If x < y:
    • If x == 0 and y == 2 (Fire vs Earth), return 1 (Fire wins)
    • Otherwise return -1 (the smaller number loses)
  • If x > y:
    • If x == 2 and y == 0 (Earth vs Fire), return -1 (Earth loses)
    • Otherwise return 1 (the larger number wins)

Main DFS Function: The dfs(i, j, k) function computes the number of winning sequences for Bob:

  • Parameters:

    • i: current round index (0 to n-1)
    • j: score difference (Alice's score - Bob's score)
    • k: Bob's last summoned creature (-1 if no previous creature)

  • Base Cases:

    1. If len(s) - i <= j: Bob cannot catch up even if he wins all remaining rounds, return 0
    2. If i >= len(s): All rounds completed
      • Return 1 if j < 0 (Bob has more points)
      • Return 0 otherwise

  • Recursive Case: For each possible creature Bob can summon (0, 1, 2):

    • Skip if it equals k (previous creature)
    • Calculate new score difference: j + calc(d[s[i]], l)
      • d[s[i]] is Alice's creature this round
      • l is Bob's chosen creature
      • The result updates the score difference
    • Recursively call dfs(i + 1, new_j, l)
    • Sum all valid sequences modulo 10^9 + 7

Algorithm Flow:

  1. Start with dfs(0, 0, -1): round 0, score difference 0, no previous creature
  2. At each state, try all valid creatures for Bob
  3. Update score based on the matchup
  4. Recursively explore the next round
  5. Count sequences where Bob wins (final score difference < 0)
  6. Clear cache after computation and return the result

The time complexity is O(n² × 3) where n is the length of string s, as we have at most n rounds, O(n) possible score differences, and 3 possible previous creatures for each state.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example where Alice's sequence is s = "FW" (2 rounds).

Round-by-round analysis:

  • Round 1: Alice plays Fire (F)
  • Round 2: Alice plays Water (W)

We need to count all sequences where Bob wins (gets more points than Alice).

Starting state: dfs(0, 0, -1)

  • Round 0, score difference 0, Bob has no previous creature

Round 1 (i=0): Alice plays F Bob can play F, W, or E (no restriction since k=-1):

  1. Bob plays F:

    • F vs F → tie (0 points)
    • New score: 0 + 0 = 0
    • Continue with dfs(1, 0, 0) (Bob's last = F)

  2. Bob plays W:

    • W vs F → W wins (+1 for Bob)
    • New score: 0 + (-1) = -1 (negative means Bob is ahead)
    • Continue with dfs(1, -1, 1) (Bob's last = W)

  3. Bob plays E:

    • E vs F → F wins (+1 for Alice)
    • New score: 0 + 1 = 1 (positive means Alice is ahead)
    • Continue with dfs(1, 1, 2) (Bob's last = E)

Round 2 (i=1): Alice plays W For each branch from Round 1:

From branch 1 dfs(1, 0, 0) (Bob played F, score tied):

  • Bob cannot play F again (k=0)
  • Bob plays W: W vs W → tie (0), final score: 0 (tie) ❌
  • Bob plays E: E vs W → E wins (+1 for Bob), final score: -1 (Bob wins) ✓

From branch 2 dfs(1, -1, 1) (Bob played W, Bob ahead by 1):

  • Bob cannot play W again (k=1)
  • Bob plays F: F vs W → W wins (+1 for Alice), final score: 0 (tie) ❌
  • Bob plays E: E vs W → E wins (+1 for Bob), final score: -2 (Bob wins) ✓

From branch 3 dfs(1, 1, 2) (Bob played E, Alice ahead by 1):

  • Bob cannot play E again (k=2)
  • Bob plays F: F vs W → W wins (+1 for Alice), final score: 2 (Alice wins) ❌
  • Bob plays W: W vs W → tie (0), final score: 1 (Alice wins) ❌

Valid winning sequences for Bob:

  1. F→E (tie in round 1, Bob wins round 2) → Bob wins 1-0
  2. W→E (Bob wins round 1, Bob wins round 2) → Bob wins 2-0

Answer: 2 valid sequences where Bob beats Alice.

Solution Implementation

1class Solution:
2    def countWinningSequences(self, s: str) -> int:
3        """
4        Count the number of winning sequences for Bob against Alice's sequence.
5        Alice's sequence is given as string s containing 'F', 'W', 'E'.
6        Bob needs to create a sequence that beats Alice's with constraints:
7        - No consecutive elements can be the same in Bob's sequence
8        - Bob wins if his total score is positive
9        """
10      
11        def calculate_score(alice_move: int, bob_move: int) -> int:
12            """
13            Calculate the score for a single round.
14            Returns: 1 if Bob wins, -1 if Alice wins, 0 if tie
15          
16            Game rules (Rock-Paper-Scissors style):
17            - Fire (0) beats Earth (2)
18            - Water (1) beats Fire (0)  
19            - Earth (2) beats Water (1)
20            """
21            if alice_move == bob_move:
22                return 0  # Tie
23          
24            if alice_move < bob_move:
25                # Special case: Fire (0) vs Earth (2) - Fire wins
26                if alice_move == 0 and bob_move == 2:
27                    return 1
28                return -1  # Otherwise Bob wins this comparison
29          
30            # alice_move > bob_move
31            # Special case: Earth (2) vs Fire (0) - Fire wins
32            if alice_move == 2 and bob_move == 0:
33                return -1
34            return 1  # Otherwise Alice wins this comparison
35      
36        @cache
37        def count_sequences(position: int, score_difference: int, last_bob_move: int) -> int:
38            """
39            Dynamic programming function to count valid winning sequences.
40          
41            Args:
42                position: Current position in Alice's sequence
43                score_difference: Current score (Alice's score - Bob's score)
44                last_bob_move: Bob's last move (0=F, 1=W, 2=E, -1=no move yet)
45          
46            Returns:
47                Number of valid sequences from this state
48            """
49            # Pruning: If remaining rounds can't overcome the deficit
50            remaining_rounds = len(s) - position
51            if remaining_rounds <= score_difference:
52                return 0
53          
54            # Base case: Reached end of sequence
55            if position >= len(s):
56                # Bob wins if his score is higher (score_difference < 0)
57                return int(score_difference < 0)
58          
59            total_sequences = 0
60            alice_current_move = move_mapping[s[position]]
61          
62            # Try all possible moves for Bob (0=Fire, 1=Water, 2=Earth)
63            for bob_move in range(3):
64                # Skip if Bob would repeat his last move
65                if bob_move == last_bob_move:
66                    continue
67              
68                # Calculate new score after this round
69                round_score = calculate_score(alice_current_move, bob_move)
70                new_score_difference = score_difference + round_score
71              
72                # Recursively count sequences from next position
73                sequences_from_here = count_sequences(position + 1, new_score_difference, bob_move)
74                total_sequences = (total_sequences + sequences_from_here) % MOD
75          
76            return total_sequences
77      
78        # Constants
79        MOD = 10**9 + 7
80        move_mapping = {"F": 0, "W": 1, "E": 2}  # Map characters to integers
81      
82        # Start the recursion from position 0, score 0, no previous move (-1)
83        result = count_sequences(0, 0, -1)
84      
85        # Clear the cache to free memory
86        count_sequences.cache_clear()
87      
88        return result
89
1class Solution {
2    private int sequenceLength;
3    private char[] inputSequence;
4    private int[] charToMoveType = new int[26];  // Maps character to move type (0=F, 1=W, 2=E)
5    private Integer[][][] memoization;  // [position][score+offset][lastMove]
6    private final int MOD = (int) 1e9 + 7;
7
8    public int countWinningSequences(String s) {
9        // Initialize move type mappings
10        // F (Fire) = 0 (default), W (Water) = 1, E (Earth) = 2
11        charToMoveType['W' - 'A'] = 1;
12        charToMoveType['E' - 'A'] = 2;
13      
14        // Convert input string to char array for faster access
15        this.inputSequence = s.toCharArray();
16        this.sequenceLength = this.inputSequence.length;
17      
18        // Initialize memoization array
19        // Dimensions: [position][score with offset][last move type]
20        // Score is offset by sequenceLength to handle negative scores
21        this.memoization = new Integer[sequenceLength][2 * sequenceLength + 1][4];
22      
23        // Start DFS with initial position 0, neutral score (offset), and no previous move (3)
24        return dfs(0, sequenceLength, 3);
25    }
26
27    /**
28     * Recursive function to count winning sequences
29     * @param currentPosition Current position in the sequence
30     * @param scoreWithOffset Current score with offset (offset = sequenceLength to handle negatives)
31     * @param lastMoveType Type of the last move played (0-2 for moves, 3 for initial state)
32     * @return Number of winning sequences from current state
33     */
34    private int dfs(int currentPosition, int scoreWithOffset, int lastMoveType) {
35        // Pruning: if remaining positions can't overcome current deficit
36        int actualScore = scoreWithOffset - sequenceLength;
37        int remainingPositions = sequenceLength - currentPosition;
38        if (remainingPositions <= actualScore) {
39            return 0;  // Cannot win even if we win all remaining rounds
40        }
41      
42        // Base case: reached end of sequence
43        if (currentPosition >= sequenceLength) {
44            // Return 1 if score is positive (winning), 0 otherwise
45            return actualScore < 0 ? 1 : 0;  // Note: negative actualScore means we're winning
46        }
47      
48        // Check memoization
49        if (memoization[currentPosition][scoreWithOffset][lastMoveType] != null) {
50            return memoization[currentPosition][scoreWithOffset][lastMoveType];
51        }
52
53        int totalWinningSequences = 0;
54      
55        // Try all possible moves (0=Fire, 1=Water, 2=Earth)
56        for (int currentMove = 0; currentMove < 3; currentMove++) {
57            // Cannot repeat the same move consecutively
58            if (currentMove == lastMoveType) {
59                continue;
60            }
61          
62            // Get opponent's move type from input sequence
63            int opponentMove = charToMoveType[inputSequence[currentPosition] - 'A'];
64          
65            // Calculate score change for this round
66            int scoreChange = calculateRoundResult(opponentMove, currentMove);
67          
68            // Recursively count winning sequences
69            totalWinningSequences = (totalWinningSequences + 
70                dfs(currentPosition + 1, scoreWithOffset + scoreChange, currentMove)) % MOD;
71        }
72      
73        // Store in memoization and return
74        memoization[currentPosition][scoreWithOffset][lastMoveType] = totalWinningSequences;
75        return totalWinningSequences;
76    }
77
78    /**
79     * Calculate the result of a single round
80     * @param opponentMove Opponent's move (0=Fire, 1=Water, 2=Earth)
81     * @param playerMove Player's move (0=Fire, 1=Water, 2=Earth)
82     * @return Score change: 1 if player wins, -1 if player loses, 0 if tie
83     */
84    private int calculateRoundResult(int opponentMove, int playerMove) {
85        // Tie case
86        if (opponentMove == playerMove) {
87            return 0;
88        }
89      
90        // Player loses cases
91        if (opponentMove < playerMove) {
92            // Special case: Fire(0) beats Earth(2)
93            if (opponentMove == 0 && playerMove == 2) {
94                return 1;  // Player wins (Earth beats Fire)
95            }
96            return -1;  // Player loses in normal cases
97        }
98      
99        // Player wins cases (opponentMove > playerMove)
100        // Special case: Earth(2) loses to Fire(0)
101        if (opponentMove == 2 && playerMove == 0) {
102            return -1;  // Player loses (Fire loses to Earth)
103        }
104        return 1;  // Player wins in normal cases
105    }
106}
107
1class Solution {
2public:
3    int countWinningSequences(string s) {
4        int n = s.size();
5      
6        // Map characters to game moves: F->0, W->1, E->2
7        int charToMove[26]{};
8        charToMove['W' - 'A'] = 1;
9        charToMove['E' - 'A'] = 2;
10        // Note: 'F' maps to 0 by default initialization
11      
12        // DP memoization table
13        // dp[position][score_offset][last_move]
14        // score_offset is shifted by n to handle negative scores
15        int dp[n][n + n + 1][4];
16        memset(dp, -1, sizeof(dp));
17      
18        // Calculate round outcome: returns 1 if player1 wins, -1 if loses, 0 if draw
19        // Game rules: Fire(0) beats Earth(2), Earth(2) beats Water(1), Water(1) beats Fire(0)
20        auto calculateRoundResult = [](int move1, int move2) -> int {
21            if (move1 == move2) {
22                return 0;  // Draw
23            }
24            if (move1 < move2) {
25                // move1 wins only if Fire(0) vs Earth(2)
26                return (move1 == 0 && move2 == 2) ? 1 : -1;
27            }
28            // move1 > move2: move1 wins unless Earth(2) vs Fire(0)
29            return (move1 == 2 && move2 == 0) ? -1 : 1;
30        };
31      
32        const int MOD = 1e9 + 7;
33      
34        // DFS with memoization
35        // i: current position in string
36        // scoreOffset: current score difference + n (to handle negative indices)
37        // lastMove: Bob's last move (0=Fire, 1=Water, 2=Earth, 3=no previous move)
38        auto dfs = [&](this auto&& dfs, int position, int scoreOffset, int lastMove) -> int {
39            // Pruning: if remaining rounds can't make Bob lose (Alice win)
40            // Bob's current deficit is (scoreOffset - n), need this to be negative
41            if (n - position <= scoreOffset - n) {
42                return 0;
43            }
44          
45            // Base case: all rounds completed
46            if (position >= n) {
47                // Bob wins if his score is positive (scoreOffset - n < 0 means Alice leads)
48                return (scoreOffset - n < 0) ? 1 : 0;
49            }
50          
51            // Check memoization
52            if (dp[position][scoreOffset][lastMove] != -1) {
53                return dp[position][scoreOffset][lastMove];
54            }
55          
56            int totalWays = 0;
57          
58            // Try all possible moves for Bob (0=Fire, 1=Water, 2=Earth)
59            for (int currentMove = 0; currentMove < 3; ++currentMove) {
60                // Bob can't repeat the same move consecutively
61                if (currentMove == lastMove) {
62                    continue;
63                }
64              
65                // Alice's move at this position
66                int aliceMove = charToMove[s[position] - 'A'];
67              
68                // Calculate new score after this round
69                int roundResult = calculateRoundResult(aliceMove, currentMove);
70              
71                // Recursively count winning sequences
72                totalWays = (totalWays + dfs(position + 1, 
73                                            scoreOffset + roundResult, 
74                                            currentMove)) % MOD;
75            }
76          
77            // Memoize and return result
78            return dp[position][scoreOffset][lastMove] = totalWays;
79        };
80      
81        // Start DFS: position 0, score offset n (neutral), no previous move (3)
82        return dfs(0, n, 3);
83    }
84};
85
1function countWinningSequences(s: string): number {
2    const n = s.length;
3  
4    // Map characters to game moves: F->0, W->1, E->2
5    const charToMove: number[] = new Array(26).fill(0);
6    charToMove['W'.charCodeAt(0) - 'A'.charCodeAt(0)] = 1;
7    charToMove['E'.charCodeAt(0) - 'A'.charCodeAt(0)] = 2;
8    // Note: 'F' maps to 0 by default initialization
9  
10    // DP memoization table
11    // dp[position][scoreOffset][lastMove]
12    // scoreOffset is shifted by n to handle negative scores
13    const dp: number[][][] = Array(n)
14        .fill(null)
15        .map(() => 
16            Array(n + n + 1)
17                .fill(null)
18                .map(() => Array(4).fill(-1))
19        );
20  
21    // Calculate round outcome: returns 1 if player1 wins, -1 if loses, 0 if draw
22    // Game rules: Fire(0) beats Earth(2), Earth(2) beats Water(1), Water(1) beats Fire(0)
23    const calculateRoundResult = (move1: number, move2: number): number => {
24        if (move1 === move2) {
25            return 0;  // Draw
26        }
27        if (move1 < move2) {
28            // move1 wins only if Fire(0) vs Earth(2)
29            return (move1 === 0 && move2 === 2) ? 1 : -1;
30        }
31        // move1 > move2: move1 wins unless Earth(2) vs Fire(0)
32        return (move1 === 2 && move2 === 0) ? -1 : 1;
33    };
34  
35    const MOD = 1e9 + 7;
36  
37    // DFS with memoization
38    // position: current position in string
39    // scoreOffset: current score difference + n (to handle negative indices)
40    // lastMove: Bob's last move (0=Fire, 1=Water, 2=Earth, 3=no previous move)
41    const dfs = (position: number, scoreOffset: number, lastMove: number): number => {
42        // Pruning: if remaining rounds can't make Bob lose (Alice win)
43        // Bob's current deficit is (scoreOffset - n), need this to be negative
44        if (n - position <= scoreOffset - n) {
45            return 0;
46        }
47      
48        // Base case: all rounds completed
49        if (position >= n) {
50            // Bob wins if his score is positive (scoreOffset - n < 0 means Alice leads)
51            return (scoreOffset - n < 0) ? 1 : 0;
52        }
53      
54        // Check memoization
55        if (dp[position][scoreOffset][lastMove] !== -1) {
56            return dp[position][scoreOffset][lastMove];
57        }
58      
59        let totalWays = 0;
60      
61        // Try all possible moves for Bob (0=Fire, 1=Water, 2=Earth)
62        for (let currentMove = 0; currentMove < 3; currentMove++) {
63            // Bob can't repeat the same move consecutively
64            if (currentMove === lastMove) {
65                continue;
66            }
67          
68            // Alice's move at this position
69            const aliceMove = charToMove[s.charCodeAt(position) - 'A'.charCodeAt(0)];
70          
71            // Calculate new score after this round
72            const roundResult = calculateRoundResult(aliceMove, currentMove);
73          
74            // Recursively count winning sequences
75            totalWays = (totalWays + dfs(position + 1, 
76                                        scoreOffset + roundResult, 
77                                        currentMove)) % MOD;
78        }
79      
80        // Memoize and return result
81        dp[position][scoreOffset][lastMove] = totalWays;
82        return totalWays;
83    };
84  
85    // Start DFS: position 0, score offset n (neutral), no previous move (3)
86    return dfs(0, n, 3);
87}
88

Time and Space Complexity

The time complexity is O(n^2 × k), where n is the length of the string s, and k = 3 represents the number of possible moves (F, W, E).

Time Complexity Analysis:

  • The dfs function has three parameters: i (position in string), j (score difference), and k (last move used)
  • Parameter i ranges from 0 to n-1, giving us n possible values
  • Parameter j represents the score difference between Bob and Alice. In the worst case, Bob wins or loses all rounds, so j ranges from -n to n, giving us 2n+1 = O(n) possible values
  • Parameter k represents the last move and has k = 3 possible values (plus the initial -1)
  • For each state (i, j, k), we iterate through at most k-1 = 2 moves (excluding the previous move)
  • Total number of states: O(n × n × k) = O(n^2 × k)
  • Work per state: O(k) for the loop
  • Total time complexity: O(n^2 × k × k) = O(n^2 × k^2) where k = 3

The space complexity is O(n^2 × k), where n is the length of the string s, and k = 3.

Space Complexity Analysis:

  • The @cache decorator memoizes all unique calls to dfs(i, j, k)
  • As analyzed above, there are O(n × n × k) = O(n^2 × k) unique states
  • Each cached entry stores an integer result
  • The recursion depth is at most n (going through the entire string)
  • Total space complexity: O(n^2 × k) for the cache plus O(n) for recursion stack, which simplifies to O(n^2 × k)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Score Calculation Logic

The most common pitfall is misunderstanding the scoring rules and implementing the wrong winner determination in the calculate_score function. The rock-paper-scissors pattern with Fire, Water, and Earth can be confusing when mapping to numerical comparisons.

Pitfall Example:

# WRONG: Assuming simple circular comparison
def calculate_score(alice_move, bob_move):
    if alice_move == bob_move:
        return 0
    return 1 if (bob_move - alice_move) % 3 == 1 else -1

Solution: The correct implementation needs to handle the special cases where Fire (0) beats Earth (2):

def calculate_score(alice_move, bob_move):
    if alice_move == bob_move:
        return 0
  
    # Handle the wrap-around case: Fire (0) beats Earth (2)
    if alice_move == 0 and bob_move == 2:
        return -1  # Alice wins
    if alice_move == 2 and bob_move == 0:
        return 1   # Bob wins
  
    # Normal cases: higher number beats lower number
    return 1 if alice_move > bob_move else -1

2. Score Difference Sign Confusion

Another critical pitfall is mixing up whether the score difference represents "Alice - Bob" or "Bob - Alice", leading to incorrect win condition checks.

Pitfall Example:

# WRONG: Confusing the sign of score difference
if position >= len(s):
    return int(score_difference > 0)  # Wrong condition!

Solution: Be consistent with the score difference representation. If tracking Alice's score - Bob's score, then Bob wins when this value is negative:

# Correct: Bob wins when Alice's score - Bob's score < 0
if position >= len(s):
    return int(score_difference < 0)

3. Forgetting the Modulo Operation

When counting large numbers of sequences, intermediate results can overflow. Forgetting to apply modulo at each step can cause incorrect results or overflow errors.

Pitfall Example:

# WRONG: Only applying modulo at the end
total_sequences = 0
for bob_move in range(3):
    if bob_move != last_bob_move:
        total_sequences += count_sequences(...)
return total_sequences % MOD  # Too late!

Solution: Apply modulo operation during accumulation to prevent overflow:

total_sequences = 0
for bob_move in range(3):
    if bob_move != last_bob_move:
        sequences = count_sequences(...)
        total_sequences = (total_sequences + sequences) % MOD
return total_sequences

4. Incorrect Pruning Condition

The pruning optimization can backfire if implemented incorrectly, causing valid winning sequences to be missed.

Pitfall Example:

# WRONG: Too aggressive pruning
if remaining_rounds < score_difference:  # Should be <=
    return 0

Solution: The correct pruning condition should check if Bob can't win even if he wins all remaining rounds:

# Bob needs to overcome a deficit of 'score_difference'
# Each win gives him +2 relative points (he gains 1, Alice gains 0)
if remaining_rounds <= score_difference:
    return 0

5. Off-by-One Error in Base Case

Checking the wrong boundary condition can lead to missing the last round or processing beyond the sequence length.

Pitfall Example:

# WRONG: Using wrong comparison
if position > len(s):  # Should be >=
    return int(score_difference < 0)

Solution: Use the correct boundary check:

if position >= len(s):  # Correct: position starts at 0
    return int(score_difference < 0)
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More