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 <= 1000s[i] is one of 'F', 'W' or 'E'
Hints for Count The Number of Winning Sequences
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.
Hint 2
Let
dp[i][last][diff]count Bob's sequences over the firstirounds ending withlastand with Bob ahead bydiff(which may be negative — shift it byn).Hint 3
Each round, extend every state with the two creatures different from
last, adjustingdiffby +1, 0 or -1. The answer sums the states withdiff > 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
- Number the creatures F = 0, W = 1, E = 2; then Bob's
bbeats Alice'saexactly when(b - a) mod 3 = 1, and loses when it is 2. - Initialise round 0: for each
b, one sequence with leaddelta(b, s[0]). - For each later round, for every state
(last, lead)with a non-zero count and everyb != last, add the count to(b, lead + delta(b, s[i]))modulo10^9 + 7. - 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
nwhen 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 % MODJava
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