Count the number of winning sequences

String Dynamic Programming

32.0% acceptance

Feb 23, 2026

103

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

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn count_winning_sequences(s: String) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = s.len();
    let s: Vec<u8> = s.bytes().collect();
    
    // score[bob_move][alice_move]: +1 if bob wins, -1 if alice wins, 0 if tie
    let score = |bob: usize, alice: usize| -> i32 {
      // 0=F, 1=W, 2=E
      // F(0) beats E(2), W(1) beats F(0), E(2) beats W(1)
      // Bob wins if bob == (alice + 1) % 3
      if bob == (alice + 1) % 3 { 1 }
      else if alice == (bob + 1) % 3 { -1 }
      else { 0 }
    };
    
    let char_to_idx = |c: u8| match c { b'F' => 0, b'W' => 1, _ => 2 };
    
    // dp[last_bob][diff] where diff = bob_points - alice_points (offset by n)
    // diff ranges from -n to n, offset by n to make 0..2n+1
    let offset = n as i64;
    let sz = 2 * n + 1;
    // dp[last_move][diff_offset] = number of sequences
    let mut dp = vec![vec![0i64; sz]; 3];
    
    // First round: all 3 choices for Bob
    let alice0 = char_to_idx(s[0]);
    for bob0 in 0..3 {
      let d = score(bob0, alice0);
      let idx = (offset + d as i64) as usize;
      dp[bob0][idx] = (dp[bob0][idx] + 1) % MOD;
    }
    
    for i in 1..n {
      let alice_i = char_to_idx(s[i]);
      let mut ndp = vec![vec![0i64; sz]; 3];
      for last in 0..3 {
        for diff_idx in 0..sz {
          if dp[last][diff_idx] == 0 { continue; }
          let cnt = dp[last][diff_idx];
          for bob_i in 0..3 {
            if bob_i == last { continue; }
            let d = score(bob_i, alice_i);
            let new_diff = diff_idx as i64 + d as i64;
            if new_diff >= 0 && new_diff < sz as i64 {
              ndp[bob_i][new_diff as usize] = (ndp[bob_i][new_diff as usize] + cnt) % MOD;
            }
          }
        }
      }
      dp = ndp;
    }
    
    // Count sequences where bob_points > alice_points, i.e., diff > 0 i.e. diff_idx > offset
    let mut result = 0i64;
    for last in 0..3 {
      for diff_idx in (offset as usize + 1)..sz {
        result = (result + dp[last][diff_idx]) % MOD;
      }
    }
    result as i32
  }
}