3320. Count The Number of Winning Sequences LeetCode Solution
In this guide, you will get 3320. Count The Number of Winning Sequences LeetCode Solution with the best time and space complexity. The solution to Count The Number of Winning Sequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count The Number of Winning Sequences
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:
If s[i] == ‘F’, Alice summons a Fire Dragon.
If s[i] == ‘W’, Alice summons a Water Serpent.
If s[i] == ‘E’, Alice summons an Earth Golem.
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 109 + 7.
Input: s = “FFF”
Output: 3
Explanation:
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
Explanation:
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'.
Complexity Analysis
Time Complexity: O(3n^2) = O(n^2)
Space Complexity: O(3n^2) = O(n^2)
3320. Count The Number of Winning Sequences LeetCode Solution in C++
class Solution {
public:
int countWinningSequences(string s) {
vector<vector<vector<int>>> mem(
s.length(), vector<vector<int>>(3, vector<int>(2 * s.length(), -1)));
const long ans = count(s, 0, 0, 0, mem) + count(s, 0, 1, 0, mem) +
count(s, 0, 2, 0, mem);
return (ans / 2) % kMod;
}
private:
static constexpr int kMod = 1'000'000'007;
// Returns the number of distinct sequences Bob can use to beat Alice for
// s[i..n), where the previous character is `prev` (0: F, 1: W, 2: E) and the
// number of points that Bob is having is `bob`.
long count(const string& s, int i, int prev, int bob,
vector<vector<vector<int>>>& mem) {
if (i == s.length())
return bob > 0 ? 1 : 0;
// Map [-s.length(), s.length() - 1] to [0, 2 * s.length() - 1].
int& res = mem[i][prev][bob + s.length()];
if (res != -1)
return res;
long f = 0; // If Bob summons a Fire Dragon at i.
long w = 0; // If Bob summons a Water Serpent at i.
long e = 0; // If Bob summons a Earth Golem at i.
switch (s[i]) {
case 'F':
if (prev != 0)
f = count(s, i + 1, 0, bob, mem) % kMod;
if (prev != 1)
w = count(s, i + 1, 1, bob + 1, mem) % kMod;
if (prev != 2)
e = count(s, i + 1, 2, bob - 1, mem) % kMod;
break;
case 'W':
if (prev != 0)
f = count(s, i + 1, 0, bob - 1, mem) % kMod;
if (prev != 1)
w = count(s, i + 1, 1, bob, mem) % kMod;
if (prev != 2)
e = count(s, i + 1, 2, bob + 1, mem) % kMod;
break;
case 'E':
if (prev != 0)
f = count(s, i + 1, 0, bob + 1, mem) % kMod;
if (prev != 1)
w = count(s, i + 1, 1, bob - 1, mem) % kMod;
if (prev != 2)
e = count(s, i + 1, 2, bob, mem) % kMod;
default:
break;
}
return res = f + w + e;
}
}; /* code provided by PROGIEZ */
3320. Count The Number of Winning Sequences LeetCode Solution in Java
class Solution {
public int countWinningSequences(String s) {
Long[][][] mem = new Long[s.length()][3][2 * s.length()];
final long ans = count(s, 0, 0, 0, mem) + count(s, 0, 1, 0, mem) + count(s, 0, 2, 0, mem);
return (int) ((ans / 2) % kMod);
}
private static final int kMod = 1_000_000_007;
// Returns the number of distinct sequences Bob can use to beat Alice for
// s[i..n), where the previous character is `prev` (0: F, 1: W, 2: E) and the
// number of points that Bob is having is `bob`.
private long count(final String s, int i, int prev, int bob, Long[][][] mem) {
if (i == s.length())
return bob > 0 ? 1 : 0;
final int bobIdx = bob + s.length();
if (mem[i][prev][bobIdx] != null)
return mem[i][prev][bobIdx];
long f = 0; // If Bob summons a Fire Dragon at i.
long w = 0; // If Bob summons a Water Serpent at i.
long e = 0; // If Bob summons a Earth Golem at i.
switch (s.charAt(i)) {
case 'F':
if (prev != 0)
f = count(s, i + 1, 0, bob, mem) % kMod;
if (prev != 1)
w = count(s, i + 1, 1, bob + 1, mem) % kMod;
if (prev != 2)
e = count(s, i + 1, 2, bob - 1, mem) % kMod;
break;
case 'W':
if (prev != 0)
f = count(s, i + 1, 0, bob - 1, mem) % kMod;
if (prev != 1)
w = count(s, i + 1, 1, bob, mem) % kMod;
if (prev != 2)
e = count(s, i + 1, 2, bob + 1, mem) % kMod;
break;
case 'E':
if (prev != 0)
f = count(s, i + 1, 0, bob + 1, mem) % kMod;
if (prev != 1)
w = count(s, i + 1, 1, bob - 1, mem) % kMod;
if (prev != 2)
e = count(s, i + 1, 2, bob, mem) % kMod;
break;
default:
break;
}
return mem[i][prev][bobIdx] = f + w + e;
}
} // code provided by PROGIEZ
3320. Count The Number of Winning Sequences LeetCode Solution in Python
class Solution:
def countWinningSequences(self, s: str) -> int:
kMod = 1_000_000_007
@functools.lru_cache(None)
def dp(i: int, prev: int, bob: int) -> int:
"""
Returns the number of distinct sequences Bob can use to beat Alice for
s[i..n), where the previous character is `prev` (0: F, 1: W, 2: E) and the
number of points that Bob is having is `bob`.
"""
if i == len(s):
return int(bob > 0)
f = 0 # If Bob summons a Fire Dragon at i.
w = 0 # If Bob summons a Water Serpent at i.
e = 0 # If Bob summons a Earth Golem at i.
match s[i]:
case 'F':
if prev != 0:
f = dp(i + 1, 0, bob) % kMod
if prev != 1:
w = dp(i + 1, 1, bob + 1) % kMod
if prev != 2:
e = dp(i + 1, 2, bob - 1) % kMod
case 'W':
if prev != 0:
f = dp(i + 1, 0, bob - 1) % kMod
if prev != 1:
w = dp(i + 1, 1, bob) % kMod
if prev != 2:
e = dp(i + 1, 2, bob + 1) % kMod
case 'E':
if prev != 0:
f = dp(i + 1, 0, bob + 1) % kMod
if prev != 1:
w = dp(i + 1, 1, bob - 1) % kMod
if prev != 2:
e = dp(i + 1, 2, bob) % kMod
return f + w + e
return (dp(0, 0, 0) + dp(0, 1, 0) + dp(0, 2, 0)) // 2 % kMod # code by PROGIEZ
