JP Morgan OA 2024 - Jack and Jones

Jack and Jones are two hackers playing a fun game. They are given a query array of non-empty strings. Each string in this array signifies a single round of the game. For each round, return an array of strings denoting the winner of that round.

Rules:

1. Jack always plays the first turn.
2. Jack selects a substring from the string which contains an odd number of vowels and removes it from the original string.
3. Jones plays next. He selects a substring that contains an even number of vowels (not zero) and removes it from the original string.
4. The game continues until neither player can make a valid move. The player who cannot make a move loses the round.
5. Both players play optimally to maximize their chances of winning.

For each string in the query array, determine whether Jack or Jones wins the round.

Example:

Input:

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

Output:

["Jack", "Jack", "Jones"]

Explanation:

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

Constraints:

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