Count The Number of Winning Sequences solution and explanation

MOD = 1000000007

def countWinningSequences(s):
    n = len(s)
    dp = [[[0] * 3 for _ in range(n)] for _ in range(3)]  # 3 x n x 3
    
    def get_index(c):
        if c == 'F': return 0
        if c == 'W': return 1
        return 2

    # Set initial possible choices for the first Bob move
    for j in range(3):
        if j != get_index(s[0]):
            dp[get_index(s[0])][0][j] = 1

    # Fill dp table
    for i in range(1, n):
        for a in range(3):
            for b in range(3):
                if b == get_index(s[i]):
                    continue
                for c in range(3):
                    if c != b:
                        dp[get_index(s[i])][i][b] = (dp[get_index(s[i])][i][b] + dp[a][i-1][c]) % MOD

    # Calculate the total winning sequences
    res = 0
    for a in range(3):
        for b in range(3):
            res = (res + dp[a][n-1][b]) % MOD
    return res

# Example usage
s = "FWEFW"
print(countWinningSequences(s))

const MOD = 1000000007;

function getCreatureIndex(c) {
  if (c === 'F') return 0;
  if (c === 'W') return 1;
  return 2;
}

function countWinningSequences(s) {
  let n = s.length;
  let dp = Array.from({length: 3}, () => Array.from({length: n}, () => Array(3).fill(0)));

  // Initialize the first round
  for (let j = 0; j < 3; j++) {
    if (j !== getCreatureIndex(s[0])) {
      dp[getCreatureIndex(s[0])][0][j] = 1;
    }
  }

  // Fill DP table
  for (let i = 1; i < n; i++) {
    for (let a = 0; a < 3; a++) {
      for (let b = 0; b < 3; b++) {
        if (b === getCreatureIndex(s[i])) continue;
        for (let c = 0; c < 3; c++) {
          if (c !== b) {
            dp[getCreatureIndex(s[i])][i][b] = (dp[getCreatureIndex(s[i])][i][b] + dp[a][i-1][c]) % MOD;
          }
        }
      }
    }
  }

  // Calculate result
  let res = 0;
  for (let a = 0; a < 3; a++) {
    for (let b = 0; b < 3; b++) {
      res = (res + dp[a][n-1][b]) % MOD;
    }
  }
  return res;
}

// Example usage
let s = 'FWEFW';
console.log(countWinningSequences(s));

import java.util.*;

public class WinningSequences {
    private static final int MOD = 1000000007;
    
    private static int getCreatureIndex(char c) {
        return (c == 'F') ? 0 : (c == 'W') ? 1 : 2;
    }

    private static int backtrack(String s, int round, int lastBob, int aliceScore, int bobScore, int[][][] memo) {
        if (round == s.length()) return (bobScore > aliceScore) ? 1 : 0;
        if (memo[round][lastBob][bobScore > aliceScore ? 1 : 0] != -1)
            return memo[round][lastBob][bobScore > aliceScore ? 1 : 0];
        int res = 0;
        int aliceMove = getCreatureIndex(s.charAt(round));
        for (int bobMove = 0; bobMove < 3; ++bobMove) {
            if (bobMove == lastBob) continue;
            int newBobScore = bobScore;
            if ((aliceMove == 0 && bobMove == 1) || (aliceMove == 1 && bobMove == 2) || (aliceMove == 2 && bobMove == 0)) {
                ++newBobScore;
            }
            res = (res + backtrack(s, round + 1, bobMove, aliceScore + (bobMove == aliceMove ? 0 : 1), newBobScore, memo)) % MOD;
        }
        return memo[round][lastBob][bobScore > aliceScore ? 1 : 0] = res;
    }

    public static int countWinningSequences(String s) {
        int[][][] memo = new int[s.length()][3][2];
        for (int[][] mat : memo) for (int[] row : mat) Arrays.fill(row, -1);
        return backtrack(s, 0, -1, 0, 0, memo);
    }

    public static void main(String[] args) {
        String s = "FWEFW";
        System.out.println(countWinningSequences(s));
    }
}

#include <iostream>
#include <vector>
#include <map>
using namespace std;

const int MOD = 1000000007;

int getCreatureIndex(char c) {
    if (c == 'F') return 0;
    if (c == 'W') return 1;
    return 2;
}

int backtrack(string &s, int round, int lastBob, int aliceScore, int bobScore, vector<vector<vector<int>>> &memo) {
    if (round == s.size()) return bobScore > aliceScore ? 1 : 0;
    if (memo[round][lastBob][bobScore > aliceScore ? 1 : 0] != -1)
        return memo[round][lastBob][bobScore > aliceScore ? 1 : 0];
    int res = 0;
    int aliceMove = getCreatureIndex(s[round]);
    for (int bobMove = 0; bobMove < 3; ++bobMove) {
        if (bobMove == lastBob) continue;
        int newBobScore = bobScore;
        if ((aliceMove == 0 && bobMove == 1) || (aliceMove == 1 && bobMove == 2) || (aliceMove == 2 && bobMove == 0)) {
            ++newBobScore;
        }
        res = (res + backtrack(s, round + 1, bobMove, aliceScore + (bobMove == aliceMove ? 0 : 1), newBobScore, memo)) % MOD;
    }
    return memo[round][lastBob][bobScore > aliceScore ? 1 : 0] = res;
}

int countWinningSequences(string s) {
    vector<vector<vector<int>>> memo(s.size(), vector<vector<int>>(3, vector<int>(2, -1)));
    return backtrack(s, 0, -1, 0, 0, memo);
}

int main() {
    string s = "FWEFW";
    cout << countWinningSequences(s) << endl;
    return 0;
}

func countWinningSequences(s string) int {
	const mod int = 1e9 + 7
	d := [26]int{}
	d['W'-'A'] = 1
	d['E'-'A'] = 2
	n := len(s)
	f := make([][][4]int, n)
	for i := range f {
		f[i] = make([][4]int, n+n+1)
		for j := range f[i] {
			for k := range f[i][j] {
				f[i][j][k] = -1
			}
		}
	}
	calc := func(x, y int) int {
		if x == y {
			return 0
		}
		if x < y {
			if x == 0 && y == 2 {
				return 1
			}
			return -1
		}
		if x == 2 && y == 0 {
			return -1
		}
		return 1
	}
	var dfs func(int, int, int) int
	dfs = func(i, j, k int) int {
		if n-i <= j-n {
			return 0
		}
		if i >= n {
			if j-n < 0 {
				return 1
			}
			return 0
		}
		if v := f[i][j][k]; v != -1 {
			return v
		}
		ans := 0
		for l := 0; l < 3; l++ {
			if l == k {
				continue
			}
			ans = (ans + dfs(i+1, j+calc(d[s[i]-'A'], l), l)) % mod
		}
		f[i][j][k] = ans
		return ans
	}
	return dfs(0, n, 3)
}