Code : Count The Number of Winning Sequences

class Solution {
  public:
    int countWinningSequences(string s);
};

int get_bob_score(char alice, char bob) {
    if (alice == bob) {
        return 0;
    }
    if ((bob == 'F' && alice == 'E') || (bob == 'E' && alice == 'W') ||
        (bob == 'W' && alice == 'F')) {
        return 1;
    }
    return -1;
}

int Solution::countWinningSequences(string str) {
    int n = str.size();
    vector<char> moves = {'F', 'E', 'W'};

    map<pair<int, char>, int> dp;
    // dp[{d, lst}] is the number of configurations which achieve score
    // difference as d when Bob's last move was lst.
    for (char now : moves) {
        int score = get_bob_score(str[0], now);
        dp[{score, now}] = 1;
    }

    for (int i = 1; i < n; i++) {
        map<pair<int, char>, int> ndp;
        for (int d = -n; d <= n; d++) {
            for (char lst : moves) {
                for (char now : moves) {
                    if (lst == now) {
                        continue;
                    }
                    int score = get_bob_score(str[i], now);
                    ndp[{d + score, now}] += dp[{d, lst}];
                }
            }
        }
        swap(dp, ndp);
    }

    int ans = 0;
    for (int d = 1; d <= n; d++) {
        for (char lst : moves) {
            ans += dp[{d, lst}];
        }
    }
    return ans;
}

const int mod = (int)1e9 + 7;
void add(int &a, int b) {
    a += b;
    a %= mod;
}

class Solution {
  public:
    int countWinningSequences(string s);
};

int get_bob_score(char alice, char bob) {
    if (alice == bob) {
        return 0;
    }
    if ((bob == 'F' && alice == 'E') || (bob == 'E' && alice == 'W') ||
        (bob == 'W' && alice == 'F')) {
        return 1;
    }
    return -1;
}

int Solution::countWinningSequences(string str) {
    int n = str.size();
    vector<char> moves = {'F', 'E', 'W'};

    map<pair<int, char>, int> dp;
    // dp[{d, lst}] is the number of configurations which achieve score
    // difference as d when Bob's last move was lst.
    for (char now : moves) {
        int score = get_bob_score(str[0], now);
        dp[{score, now}] = 1;
    }

    for (int i = 1; i < n; i++) {
        map<pair<int, char>, int> ndp;
        for (int d = -n; d <= n; d++) {
            for (char lst : moves) {
                for (char now : moves) {
                    if (lst == now || dp[{d, lst}] == 0) {
                        continue;
                    }
                    int score = get_bob_score(str[i], now);
                    add(ndp[{d + score, now}], dp[{d, lst}]);
                }
            }
        }
        swap(dp, ndp);
    }

    int ans = 0;
    for (int d = 1; d <= n; d++) {
        for (char lst : moves) {
            add(ans, dp[{d, lst}]);
        }
    }
    return ans;
}

const int mod = (int)1e9 + 7;
void add(int &a, int b) {
    a += b;
    a %= mod;
}

class Solution {
  public:
    int countWinningSequences(string s);
};

int get_bob_score(char alice, char bob) {
    if (alice == bob) {
        return 0;
    }
    if ((bob == 'F' && alice == 'E') || (bob == 'E' && alice == 'W') ||
        (bob == 'W' && alice == 'F')) {
        return 1;
    }
    return -1;
}

int Solution::countWinningSequences(string str) {
    int n = str.size();
    vector<char> moves = {'F', 'E', 'W'};
    int offset = n;

    vector<vector<int>> dp(2 * n + 1, vector<int>(3, 0));
    // dp[d][lst] is the number of configurations which achieve score
    // difference as d when Bob's last move was moves[lst].
    for (int now = 0; now < moves.size(); now++) {
        int score = get_bob_score(str[0], moves[now]);
        dp[offset + score][now] = 1;
    }

    for (int i = 1; i < n; i++) {
        vector<vector<int>> ndp(2 * n + 1, vector<int>(3, 0));
        for (int d = -n; d <= n; d++) {
            for (int lst = 0; lst < moves.size(); lst++) {
                for (int now = 0; now < moves.size(); now++) {
                    if (lst == now || dp[offset + d][lst] == 0) {
                        continue;
                    }
                    int score = get_bob_score(str[i], moves[now]);
                    add(ndp[offset + d + score][now], dp[offset + d][lst]);
                }
            }
        }
        swap(dp, ndp);
    }

    int ans = 0;
    for (int d = 1; d <= n; d++) {
        for (int lst = 0; lst < moves.size(); lst++) {
            add(ans, dp[offset + d][lst]);
        }
    }
    return ans;
}