Solution 1 for Scaler Topics Fortnightly Contest - 12

This article is part of the Scaler Topics Fortnightly Contest - 12

Solution Approach

• Let $count_A$ denotes count of 'A's and $count_B$ denote count of 'B's
• Now, consider 3 cases:

1. $count_A = 0$ Alice can't make any moves, so the game ends at the very first move, with a draw.

2. $count_B = 0$ Whatever move Alice makes, she can't gain any point. So, the result would either be lose or draw.

3. $count_A > 0$ and $count_B > 0$ An optimal move for Alice is to choose all the 'A's as her subsequence in 1st move and gain point equal to count_B. Now, whatever move Bob plays, he can't gain any point, as all 'A's are removed.

• Alice would win in this case.

Time complexity: $O(N)$

Space complexity: $O(1)$

C++ Implementation

Java Implementation

Python Implementation