A String p is called anti-palindrome if p[i] doesn't equal to p[n - i - 1] for each 0 <= i < (n-1)/2, where n is the length of p. It means that each character (except the middle in the case of a string of odd length) must be different from its symmetric character. For example, "c", "cpp", "java" are anti-palindrome, but "test", "pp" and "weather" are not.
You are given a String s. Rearrange its letters in such a way that the resulting string is anti-palindrome. If there are several solutions, return the one that comes earliest alphabetically. If it is impossible to do it, return the empty string.