Introduction

In this blog post, we will explore how to solve the LeetCode problem "3320" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. 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'.

Explanation

Here's the breakdown of the approach, complexities, and the Python code:

• High-Level Approach:

  • Use dynamic programming to calculate the number of valid Bob's sequences and the score difference (Bob's score - Alice's score).
  • The DP state will track the current round, Bob's previous move, Bob's current score advantage, and the number of sequences.
  • Iterate through possible moves for Bob in each round, considering the constraints and score updates.

• Complexity:

  • Runtime Complexity: O(n * k), where n is the length of the string s and k is the maximum possible score difference (which can be at most n).
  • Storage Complexity: O(n * k)

Code

    def solve():
    s = input()
    n = len(s)
    MOD = 10**9 + 7

    # dp[i][j][k]: number of ways to reach round i with score difference j and last move k
    # j: Bob's score - Alice's score
    # k: 0 = Fire, 1 = Water, 2 = Earth

    dp = {}

    def get_dp(i, j, k):
        if (i, j, k) in dp:
            return dp[(i, j, k)]
        else:
            return 0

    def set_dp(i, j, k, val):
        dp[(i, j, k)] = val

    # Initialize base case (round 0, score difference 0, no last move)
    set_dp(0, 0, -1, 1)  # -1 means no previous move

    for i in range(n):
        for j in range(-n, n + 1):
            for k in range(-1, 3):  # Previous move of Bob
                count = get_dp(i, j, k)
                if count == 0:
                    continue

                for bob_move in range(3):
                    if bob_move == k:
                        continue

                    alice_move = 0 if s[i] == 'F' else (1 if s[i] == 'W' else 2)

                    score_change = 0
                    if bob_move == 0 and alice_move == 2:
                        score_change = 1
                    elif bob_move == 1 and alice_move == 0:
                        score_change = 1
                    elif bob_move == 2 and alice_move == 1:
                        score_change = 1
                    elif alice_move == 0 and bob_move == 2:
                        score_change = -1
                    elif alice_move == 1 and bob_move == 0:
                        score_change = -1
                    elif alice_move == 2 and bob_move == 1:
                        score_change = -1

                    new_score = j + score_change

                    set_dp(i + 1, new_score, bob_move, (get_dp(i + 1, new_score, bob_move) + count) % MOD)

    ans = 0
    for j in range(1, n + 1):
        for k in range(3):
            ans = (ans + get_dp(n, j, k)) % MOD

    print(ans)

solve()