Learn Tech Skills from Scratch @ Scaler EDGE

# Substring Game

Problem Description

Two players Alice and Bob are playing the substring game.

In this game, there exists a string A initially, consisting only of lower-case English characters.

When a player has to make a move, he/she chooses such a substring of A that is not a palindrome, and removes it entirely such that the characters before and after the substring get concatenated and they appear in the same order.

For example, if the string A is "dabcbad" at some stage of the game, the player whose turn it is, can remove the substring "abc" as it is not a palindrome. The string thus becomes "dbad".

The string A thus changes after each move.

The player who is unable to make a move, loses. This happens when there exists no substring in A that is not a palindrome.

Alice starts the game and both player take alternate turns. Find the winner of the game if they both play optimally.

Problem Constraints

1 <= |A| <= 105

Input Format

The first and only argument of the function is the string A.

Output Format

Your function should return a string denoting the winner of the game. It should return "Alice" if Alice wins, otherwise it should return "Bob".

Example Input

Input 1:

``` A: "abd"
```

Input 2:

``` A: "n"
```

Example Output

Output 1:

``` "Alice"
```

Output 2:

``` "Bob"
```

Example Explanation

Explanation 1:

``` Alice can remove the substring "ab". Now, Bob is left with the string "d" which is a palindrome, thus he loses because he cannot make a move now.
```

Explanationn 2:

``` Alice cannot make any move in the beginning of the game, hence she loses.
```

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Hints
• Hint 1
• Solution Approach
• Complete Solution