この問題は不変量に着目することで解くことができます。

A を \(1\) 、B を \(2\) 、C を \(3\) と対応づけます。すると、異なる \(2\) 文字を削除してどちらと違う文字を挿入しても列全体の総 \(\mathrm{XOR}\) は変わりません。この総 \(\mathrm{XOR}\) を \(X\) とします。

さらに、ゲームの最終系は AAA...A のように同じ文字が何文字か残る形になります。そして、\(\mathrm{XOR}\) の性質より \(X=0\) なら最終的な文字列は偶数長、\(X\neq 0\) なら奇数長となります。この長さの偶奇は互いの操作によりません。各操作により長さの偶奇は必ず変わり、最初と最後の文字列の長さが決まっているためここから Alice と Bob のどちらが勝つかを判定することができます。

奇数回登場する文字が \(2\) 種以上あれば Alice の勝ち、そうでなければ Bob の勝ち、とも判定できます。

実装例(Python3)

import sys

input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    s = input().rstrip()
    x = 0
    for c in s:
        x ^= ord(c) - ord("A") + 1
    print("Alice" if (x != 0) != (n % 2 != 0) else "Bob")

import sys

input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    s = input()
    cnt = s.count("A") % 2 + s.count("B") % 2 + s.count("C") % 2
    print("Alice" if cnt >= 2 else "Bob")