Smallest Substring Containing All Unique Characters

You are given a string S. Your task is to find the smallest contiguous substring of S that contains every distinct character present in S exactly once.

For example, if S is "abcabcbb", the distinct characters are {a, b, c} and the smallest substring containing all of them is "abc". Similarly, for S = "aaabcdeaa", the answer is "abcde".

This problem requires you to implement a sliding window technique to dynamically maintain a window with all unique characters, and then minimize the window size while keeping the constraint valid.

Note: The problem must be solved by reading input from standard input (stdin) and writing the output to standard output (stdout).

inputFormat

The first line contains an integer T, the number of test cases. Each of the next T lines contains a non-empty string S consisting of lowercase English letters.

For each test case, S is guaranteed to have at least one character and consists of letters only.

outputFormat

For each test case, output the smallest substring that contains all the distinct characters present in S. Each result should be printed on a new line.

1
abcabcbb

abc