String Game ( DSA INTERVIEW PREPARATION PROBLEMS AND SOLUTIONS )

 Alice and Bob are playing a game on a binary string 

S$S$ of length N$N$.

Alice and Bob alternate turns, with Alice going first. On their turn, the current player must choose any index 1≤i<|S|$1\le i<|S|$ such that Si≠Si+1$S_i\ne S_{i+1}$ and erase either Si$S_i$ or Si+1$S_{i+1}$ from the string. This reduces the length of S$S$ by one, and the remaining parts of S$S$ are concatenated in the same order.

The player who is unable to make a move loses.

Determine the winner if both players play optimally.

Input Format

• The first line of input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains a single integer N$N$, the length of the string.
• The second line contains the binary string S$S$ of length N$N$.

Output Format

For each test case output Alice$Alice$ if Alice wins the game, otherwise output Bob$Bob$. The output is not case-sensitive, so for example "Bob", "boB" and "Bob" are all considered equivalent.

Constraints

• 1≤T≤1000$1\le T\le 1000$
• 2≤N≤105$2\le N\le {10}^5$
• S$S$ is a binary string
• Sum of N$N$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Sample Input 1 

3
4
1111
3
110
4
1010

Sample Output 1 

Bob
Alice
Bob

Explanation

Test Case 1$1$: There is no such index i$i$ such that Si≠Si+1$S_i\ne S_{i+1}$. So, Alice does not have any move and loses, making Bob the winner.

Test Case 2$2$: Alice can choose i=2$i=2$ (because S2=1$S_2=1$ and S3=0$S_3=0$) and remove S3$S_3$. After this move, the remaining string is "11$11$". Bob now has no moves and thus loses.

• Tweet
• Share
• Share
• Share
• Share

Related Post