Count The Number of Winning Sequences - Practice Coding Problems

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.

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⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: s = "FW"

› Output: 4

💡 Note: Bob can win with sequences WF, WE, EF, EW. For example: if Bob plays WF, scores are (W vs F: Bob+1), (F vs W: Bob+1), final 2-0.

Example 2 — Single Round

$ Input: s = "F"

› Output: 2

💡 Note: Bob can win by playing W (W beats F) or E is invalid since it loses to F. Actually Bob wins with W only, but can also play E for tie then needs score > 0. Bob wins with W and E: W beats F (+1), E loses to F but we need strictly greater.

Example 3 — All Same

$ Input: s = "FFF"

› Output: 2

💡 Note: Bob must avoid consecutive moves. He can play WEW (scores +1,0,+1 = +2) or EWE (scores 0,+1,0 = +1), both beat Alice's 0.

Constraints

1 ≤ s.length ≤ 1000
s consists only of 'F', 'W', and 'E'

Visualization

Tap to expand

Understanding the Visualization

Input

Alice's sequence s = "FW" (Fire, Water)

Process

Find all valid Bob sequences where score > Alice's score

Output

Count of distinct winning sequences for Bob

Key Takeaway

🎯 Key Insight: Use DP to efficiently count all valid Bob sequences that beat Alice's fixed strategy

Asked in

G Google 25 f Facebook 18

The key insight is to use dynamic programming to track all possible game states defined by (position, last_move, score_difference). The memoized approach efficiently counts winning sequences by avoiding redundant calculations. Time: O(n × 3 × 2n), Space: O(n × 3 × 2n)

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Dynamic Programming	O(n × 3 × 2n)	O(n × 3 × 2n)	Use memoization to avoid recalculating same states
Brute Force Recursion	O(2^n)	O(n)	Generate all possible Bob sequences and count winning ones
Optimized 2D Dynamic Programming	O(n × 3 × 2n)	O(n × 3 × 2n)	Use 2D DP table with score difference optimization

Memoized Dynamic Programming — Algorithm Steps

Define state as (position, last_creature, score_difference)
Use memoization to cache computed results
Build solution bottom-up by combining cached subproblems

Visualization

Tap to expand

Step-by-Step Walkthrough

State Definition

State = (position, last_move, score_difference)

Cache Results

Store computed results to avoid redundant calculations

Reuse Cached

Return cached result when same state is encountered

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

const int MOD = 1000000007;
const int MAXN = 1001;
const int OFFSET = 1000;

int memo[MAXN][4][2001]; // pos, lastMove (0=F,1=W,2=E,3=none), scoreDiff+OFFSET
int visited[MAXN][4][2001];

int getPoints(char aliceMove, char bobMove) {
    if (aliceMove == bobMove) return 0;
    if ((bobMove == 'F' && aliceMove == 'E') ||
        (bobMove == 'W' && aliceMove == 'F') ||
        (bobMove == 'E' && aliceMove == 'W')) {
        return 1; // Bob gets point
    }
    return -1; // Alice gets point
}

int charToInt(char c) {
    if (c == 'F') return 0;
    if (c == 'W') return 1;
    if (c == 'E') return 2;
    return 3; // none
}

int dp(const char* s, int pos, int lastMove, int scoreDiff, int n) {
    if (pos == n) {
        return scoreDiff > 0 ? 1 : 0;
    }
    
    int adjScoreDiff = scoreDiff + OFFSET;
    if (visited[pos][lastMove][adjScoreDiff]) {
        return memo[pos][lastMove][adjScoreDiff];
    }
    
    int count = 0;
    char moves[] = {'F', 'W', 'E'};
    
    for (int i = 0; i < 3; i++) {
        char move = moves[i];
        int moveInt = charToInt(move);
        
        if (pos == 0 || moveInt != lastMove) {
            int points = getPoints(s[pos], move);
            int newScoreDiff = scoreDiff + points;
            count = (count + dp(s, pos + 1, moveInt, newScoreDiff, n)) % MOD;
        }
    }
    
    visited[pos][lastMove][adjScoreDiff] = 1;
    memo[pos][lastMove][adjScoreDiff] = count;
    return count;
}

int solution(const char* s) {
    int n = strlen(s);
    memset(visited, 0, sizeof(visited));
    return dp(s, 0, 3, 0, n);
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0; // Remove newline
    
    int result = solution(s);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 3 × 2n)

n positions × 3 possible last moves × 2n possible score differences (from -n to +n)

✓ Linear Growth

Space Complexity

O(n × 3 × 2n)

Memoization table stores results for all possible states plus recursion stack

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

428 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler