I choose c++ for solving this question. and first explain the approach and then write the code. i was used map for solving. code was successfully executed and after that interviewer provide some more test case to run and that was run.