The relative order of the pieces never changes throughout the game. Since a piece may only move into an adjacent empty cell, no piece can ever jump over another. Therefore, the only changing part of the board is the size of the gaps between consecutive pieces.

Define G_A as the sum of the lengths of all interior gaps immediately to the right of every A piece (if the first piece on the board is B, the definition is symmetric and we instead consider the gaps immediately to the left of every A piece). Likewise, define G_B as the sum of the lengths of all interior gaps immediately to the left of every B piece.

Since every interior gap is counted exactly once in both definitions, we have G_A = G_B. Let G denote this common value, i.e. G = G_A = G_B.

Consider one complete round, consisting of one move by Jong followed by one move by the opponent.

During a single move, exactly one paired gap changes in length. Depending on the direction of the move, that gap either increases by 1 or decreases by 1.

Therefore, after one complete round, the value of G must become one of the following:

1. G' = G + 1 + 1 = G + 2
2. G' = G + 1 - 1 = G
3. G' = G - 1 + 1 = G
4. G' = G - 1 - 1 = G - 2

In every case, G' differs from G by an even number. Hence, the parity of G is invariant after every complete round.

A player loses if they begin their turn with no legal move.

Observe that G_A is exactly the total number of empty cells adjacent to Jong's movable side. Therefore, G_A = 0 if and only if Jong has no legal move.

If G_A is initially odd, then it remains odd at the beginning of every one of Jong's turns because its parity never changes. Since 0 is even, Jong can never begin his turn with G_A = 0. Hence, Jong can never lose.

Conversely, if G_A is initially even, then every one of Jong's turns begins with an even value of G_A. Eventually, all legal moves are exhausted, so G_A reaches 0, leaving Jong with no legal move.

Therefore, Jong wins if and only if G_A is odd.

1. Traverse the board from left to right.
2. Whenever an A or B piece is encountered, count the consecutive '_' characters immediately following it.
3. Accumulate this value into G_A.
4. If G_A is odd, output A; otherwise, output B.

• Time Complexity: O(N)
• Space Complexity: O(N)

Here are some valid solutions:

#include <stdio.h>

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n, cnt = 0;
        scanf("%d",&n);
        char s[n+1];
        scanf("%s",s);
        for(int i=0;i<n;i++){
            if(s[i] != '_'){
                i++;
                while(i < n && s[i] == '_'){
                    cnt++;
                    i++;
                }
                i--;
            }
        }
        printf("%c\n", (cnt&1 ? 'A' : 'B'));
    }
}

#include <bits/stdc++.h>

using namespace std;

int main(){
    int t;
    cin >> t;
    while(t--){
        int n, cnt = 0;
        string s;
        cin >> n >> s;
        for(int i=0;i<n;i++){
            if(s[i] != '_'){
                i++;
                while(i < n && s[i] == '_'){
                    cnt++;
                    i++;
                }
                i--;
            }
        }
        cout << (cnt&1 ? "A\n" : "B\n");
    }
}