Count The Number of Winning Sequences - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
3320. Count The Number of Winning Sequences
Hard
50 Points
String
Dynamic Programming
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:
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 109 + 7.
Examples
Example 1
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'.
3320. Count The Number of Winning Sequences
Hard
50 Points
String
Dynamic Programming
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:
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 109 + 7.
Examples
Example 1
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" .