Microsoft Online Assessment Lexicographically Smallest String Problem

Problem overview from real interview of Microsoft:

Learn how to solve the Microsoft OA problem for the lexicographically smallest string. Group indices using Union-Find to sort characters in connected components.