Alex and Bob are playing a game of Atlas (quick refresher: both players take turns in naming a country starting with the same letter as the ending letter of the last country named by the other player) Only their game is slightly different. Both players have a shared list of countries, and they can only name countries listed here. To begin, Alex selects a country from the first ‘K’ countries listed in the array. Let’s say he selects country a[i]. Then Bob selects a country from the next K entries in the array (ie. having index between i+1 and i+K inclusive) such that Bob’s country has the same starting letter as the last letter of country a[i]. The game continues in this manner. If at any point, a person cannot select any country, he loses.
Given the list of countries A[], and integer K, your task is to tell who will win the game?
N<=10^6, K<=N, O(N) solution