It is a super interesting problem - it's not about the algorithm SKILLs, it is about algorithm THINKING.
In this problem, the goal is actually to have as less matched prefix as possible. Here is the thinking process:
1. How does KMP (prefix jump table calc.) work? It always starts with the first char - only if when the first char matches, we continue counting matching.
2. Given #1, we need to reduce the matched cases # to minimum of #1 - that means, the starting char is the char with minimal freq.
3. What's next? Remember we have another requirement: lexicographically smallest, so after the char0 at #2, we can put string like this: aaaa...bb...ccc...
4. But, what if least-freq char is the smallest char, like 'a' ? string like aaaaa..aabbb will have matched count as 1+ 2 +3..., so we need to interleave the aaa...aa, with b - if avail
Strategy is: STEP BY STEP & OBSERVE