JP Morgan OA-5 2024

Problem Description

Ram and Shyam are two hackers engaged in a game. They are given a list of non-empty strings, where each string represents a round of the game. For each round, return the name of the winner as an array of strings.

Game Rules:

• Ram always takes the first turn.
• Ram must select a substring that contains an odd number of vowels and remove it from the string.
• After Ram's turn, Shyam selects a substring containing an even number of vowels (but greater than zero) and removes it from the string.
• The game alternates between Ram and Shyam until no valid moves are left. The player who cannot make a valid move loses the round.
• Both players play optimally to maximize their chances of winning.

For each string in the query list, determine the winner of the round, either "Ram" or "Shyam".

Input Format:

• query: A list of non-empty strings, each representing a round of the game.

Output Format:

• Return an array of strings, where each element is either "Ram" or "Shyam", representing the winner of the corresponding round.

Constraints:

• Each string in query contains at least one character.
• Time Complexity: Expected O(1) per round.
• Space Complexity: Expected O(1) per round.

Example:

Input:

query = ["Leetcode", "DSA", "Sphynx"]

Output:

["Ram", "Ram", "Shyam"]

Explanation:

1. Round 1: "Leetcode"
   • Ram selects the substring 'e' (odd number of vowels).
   • Shyam selects the substring 'ee' (even number of vowels).
   • Ram selects 'o' (odd number of vowels), and now the string is empty.
   • Shyam cannot make a move. Ram wins.
2. Round 2: "DSA"
   • Ram selects 'A' (odd number of vowels).
   • Now the string is empty.
   • Shyam cannot make a move. Ram wins.
3. Round 3: "Sphynx"
   • There are no vowels in the string.
   • Ram cannot make any move, so Shyam wins.