It's basically the #49, but there's one thing different that the character can be anything which is a unicode. The interviewer said it could be a very big tuple if we using the second solution, and ask me to implementation the second solution with dictionary and said that will have a O(n^2) time complexity, but I think this is not work as what he thought, as comparing a dictionary or serialize a dictionary will not be a O(n) complexity, which should as least a O(nlogn).

Does any one knows how should this work?