Count The Number of Winning Sequences

Hard
1664.

Count The Number of Winning Sequences

Count The Number of Winning Sequences is a hard coding problem on strings and dynamic programming, asked in Amazon interviews.

Alice and Bob play a game of n rounds. In each round both summon one of three creatures: a Fire Dragon ('F'), a Water Serpent ('W') or an Earth Golem ('E'). In a round:

  • Fire Dragon against Earth Golem: the Fire Dragon's player scores a point.
  • Water Serpent against Fire Dragon: the Water Serpent's player scores a point.
  • Earth Golem against Water Serpent: the Earth Golem's player scores a point.
  • The same creature on both sides: nobody scores.

You are given Alice's moves as a string s, where s[i] is her creature in round i. Bob never summons the same creature in two consecutive rounds.

Return how many different sequences of moves let Bob finish with strictly more points than Alice. Since the answer may be very large, return it modulo 10^9 + 7.

Example 1

Input
s = "FFF"
Output
3
Explanation
Bob wins with "WFW", "FWF" or "WEW".

Example 2

Input
s = "FWEFW"
Output
18

Example 3

Input
s = "E"
Output
1
Explanation
Only a Fire Dragon beats Alice's Earth Golem.

Constraints

  • 1 <= s.length <= 1000
  • s[i] is one of 'F', 'W' or 'E'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var countWinningSequences = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count The Number of Winning Sequences — Problem & Solution

Count The Number of Winning Sequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Count The Number of Winning Sequences is a hard coding problem on strings and dynamic programming, asked in Amazon interviews.

  • Difficulty: Hard
  • Topics: Strings, Dynamic Programming
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Alice and Bob play a game of n rounds. In each round both summon one of three creatures: a Fire Dragon ('F'), a Water Serpent ('W') or an Earth Golem ('E'). In a round:

  • Fire Dragon against Earth Golem: the Fire Dragon's player scores a point.
  • Water Serpent against Fire Dragon: the Water Serpent's player scores a point.
  • Earth Golem against Water Serpent: the Earth Golem's player scores a point.
  • The same creature on both sides: nobody scores.

You are given Alice's moves as a string s, where s[i] is her creature in round i. Bob never summons the same creature in two consecutive rounds.

Return how many different sequences of moves let Bob finish with strictly more points than Alice. Since the answer may be very large, return it modulo 10^9 + 7.

Example 1

Input: s = "FFF"
Output: 3
Explanation: Bob wins with "WFW", "FWF" or "WEW".

Example 2

Input: s = "FWEFW"
Output: 18

Example 3

Input: s = "E"
Output: 1
Explanation: Only a Fire Dragon beats Alice's Earth Golem.

Constraints

  • 1 <= s.length <= 1000
  • s[i] is one of 'F', 'W' or 'E'

Hints for Count The Number of Winning Sequences

  1. Hint 1

    Only two things about the past matter for the future: Bob's last creature (to avoid repeating it) and the current score difference.

  2. Hint 2

    Let dp[i][last][diff] count Bob's sequences over the first i rounds ending with last and with Bob ahead by diff (which may be negative — shift it by n).

  3. Hint 3

    Each round, extend every state with the two creatures different from last, adjusting diff by +1, 0 or -1. The answer sums the states with diff > 0.

How to solve Count The Number of Winning Sequences

A round's outcome depends only on the two creatures in it, and Bob's only constraint links consecutive rounds. So the whole history collapses into (Bob's last creature, Bob's lead), and a DP over rounds counts sequences per state.

Approach

  1. Number the creatures F = 0, W = 1, E = 2; then Bob's b beats Alice's a exactly when (b - a) mod 3 = 1, and loses when it is 2.
  2. Initialise round 0: for each b, one sequence with lead delta(b, s[0]).
  3. For each later round, for every state (last, lead) with a non-zero count and every b != last, add the count to (b, lead + delta(b, s[i])) modulo 10^9 + 7.
  4. Sum the counts of all states with lead > 0.

Why it works

Two partial sequences with the same last creature and the same lead can be extended by exactly the same continuations with the same final results, so merging them into one counted state is exact. The lead after i rounds lies in [-i, i], giving O(n) leads per round.

Complexity

  • Time — O(n^2)
  • Space — O(n)

Pitfalls

  • The lead can be negative — offset it by n when using it as an array index.
  • "Strictly more" excludes ties: a lead of 0 does not count.

Reference solution

Python

def countWinningSequences(s: str) -> int:
    MOD = 10**9 + 7
    idx = {'F': 0, 'W': 1, 'E': 2}
    n = len(s)
    off = n
    width = 2 * n + 1

    def delta(b, a):
        d = (b - a) % 3
        return 1 if d == 1 else (-1 if d == 2 else 0)

    dp = [[0] * width for _ in range(3)]
    a0 = idx[s[0]]
    for b in range(3):
        dp[b][off + delta(b, a0)] = 1
    for i in range(1, n):
        a = idx[s[i]]
        nd = [[0] * width for _ in range(3)]
        for p in range(3):
            row = dp[p]
            for x in range(off - i, off + i + 1):
                c = row[x]
                if c == 0:
                    continue
                for b in range(3):
                    if b != p:
                        y = x + delta(b, a)
                        nd[b][y] = (nd[b][y] + c) % MOD
        dp = nd
    total = 0
    for b in range(3):
        for x in range(off + 1, width):
            total += dp[b][x]
    return total % MOD

Java

static int creature(char ch) { return ch == 'F' ? 0 : ch == 'W' ? 1 : 2; }

static int delta(int b, int a) {
    int d = (b - a + 3) % 3;
    return d == 1 ? 1 : d == 2 ? -1 : 0;
}

public static int countWinningSequences(String s) {
    final int MOD = 1000000007;
    int n = s.length(), off = n, width = 2 * n + 1;
    int[][] dp = new int[3][width];
    int a0 = creature(s.charAt(0));
    for (int b = 0; b < 3; b++) dp[b][off + delta(b, a0)] = 1;
    for (int i = 1; i < n; i++) {
        int a = creature(s.charAt(i));
        int[][] nd = new int[3][width];
        for (int p = 0; p < 3; p++) {
            for (int x = off - i; x <= off + i; x++) {
                int c = dp[p][x];
                if (c == 0) continue;
                for (int b = 0; b < 3; b++) {
                    if (b == p) continue;
                    int y = x + delta(b, a);
                    nd[b][y] = (nd[b][y] + c) % MOD;
                }
            }
        }
        dp = nd;
    }
    long total = 0;
    for (int b = 0; b < 3; b++) for (int x = off + 1; x < width; x++) total += dp[b][x];
    return (int) (total % MOD);
}

C++

int countWinningSequences(string s) {
    const int MOD = 1000000007;
    auto creature = [](char ch) { return ch == 'F' ? 0 : ch == 'W' ? 1 : 2; };
    auto delta = [](int b, int a) { int d = (b - a + 3) % 3; return d == 1 ? 1 : d == 2 ? -1 : 0; };
    int n = s.size(), off = n, width = 2 * n + 1;
    vector<vector<int>> dp(3, vector<int>(width, 0));
    int a0 = creature(s[0]);
    for (int b = 0; b < 3; b++) dp[b][off + delta(b, a0)] = 1;
    for (int i = 1; i < n; i++) {
        int a = creature(s[i]);
        vector<vector<int>> nd(3, vector<int>(width, 0));
        for (int p = 0; p < 3; p++) {
            for (int x = off - i; x <= off + i; x++) {
                int c = dp[p][x];
                if (c == 0) continue;
                for (int b = 0; b < 3; b++) {
                    if (b == p) continue;
                    int y = x + delta(b, a);
                    nd[b][y] = (nd[b][y] + c) % MOD;
                }
            }
        }
        dp = nd;
    }
    long long total = 0;
    for (int b = 0; b < 3; b++) for (int x = off + 1; x < width; x++) total += dp[b][x];
    return (int) (total % MOD);
}

JavaScript

var countWinningSequences = function(s) {
    var MOD = 1000000007;
    var code = function(ch) { return ch === "F" ? 0 : ch === "W" ? 1 : 2; };
    var delta = function(b, a) { var d = (b - a + 3) % 3; return d === 1 ? 1 : d === 2 ? -1 : 0; };
    var n = s.length, off = n, width = 2 * n + 1;
    var dp = [];
    for (var b = 0; b < 3; b++) dp.push(new Array(width).fill(0));
    var a0 = code(s.charAt(0));
    for (var b0 = 0; b0 < 3; b0++) dp[b0][off + delta(b0, a0)] = 1;
    for (var i = 1; i < n; i++) {
        var a = code(s.charAt(i));
        var nd = [];
        for (var t = 0; t < 3; t++) nd.push(new Array(width).fill(0));
        for (var p = 0; p < 3; p++) {
            for (var x = off - i; x <= off + i; x++) {
                var c = dp[p][x];
                if (c === 0) continue;
                for (var b2 = 0; b2 < 3; b2++) {
                    if (b2 === p) continue;
                    var y = x + delta(b2, a);
                    nd[b2][y] = (nd[b2][y] + c) % MOD;
                }
            }
        }
        dp = nd;
    }
    var total = 0;
    for (var b3 = 0; b3 < 3; b3++) for (var z = off + 1; z < width; z++) total = (total + dp[b3][z]) % MOD;
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming