We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count The Number of Winning Sequences

Difficulty: Hard

Problem Description

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. If Alice's sequence of moves is given, determine how many distinct sequences Bob can use to beat Alice, where Bob's score must be strictly greater than Alice's score. Bob cannot summon the same creature in two consecutive rounds.

Key Insights

  • Each creature has specific winning conditions against others (Fire Dragon beats Earth Golem, Water Serpent beats Fire Dragon, Earth Golem beats Water Serpent).
  • Bob needs to strategically choose his moves based on Alice's sequence to gain more points.
  • The sequences must also respect the constraint that Bob cannot choose the same creature consecutively.
  • A dynamic programming approach can help track the possible winning sequences efficiently.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a dynamic programming approach. We maintain two arrays to keep track of the number of winning sequences Bob can have for each round, based on the last creature he summoned. For each round, we check Alice's move and update Bob's possible moves that can win against Alice's current creature. We also ensure that Bob does not repeat the same creature in consecutive rounds. Finally, we sum up all winning sequences that result in Bob having strictly more points than Alice.

Code Solutions

def countWinningSequences(s: str) -> int:
    MOD = 10**9 + 7
    n = len(s)
    
    # dp[i][j] will store the number of valid sequences for the first i rounds
    # where j is the last creature Bob summoned (0: F, 1: W, 2: E)
    dp = [[0] * 3 for _ in range(n + 1)]
    dp[0] = [1, 1, 1]  # Base case: for 0 rounds, one way to start
    
    for i in range(1, n + 1):
        if s[i - 1] == 'F':
            dp[i][0] = 0  # Bob cannot summon F
            dp[i][1] = dp[i - 1][2]  # Bob can summon W if last was E
            dp[i][2] = dp[i - 1][1]  # Bob can summon E if last was W
        elif s[i - 1] == 'W':
            dp[i][0] = dp[i - 1][2]  # Bob can summon F if last was E
            dp[i][1] = 0  # Bob cannot summon W
            dp[i][2] = dp[i - 1][0]  # Bob can summon E if last was F
        else:  # s[i - 1] == 'E'
            dp[i][0] = dp[i - 1][1]  # Bob can summon F if last was W
            dp[i][1] = dp[i - 1][0]  # Bob can summon W if last was F
            dp[i][2] = 0  # Bob cannot summon E
    
    total_sequences = sum(dp[n]) % MOD
    return total_sequences
← Back to All Questions