FastPrep
Problem · String

Rearrange String

Learn this problem
● HardIntuitOA

Problem statement

You have a string S. Your task is to rearrange some characters of the string (if needed) so that S[i] is not equal to S[L - i - 1] for each 0 <= i < (L - 1) / 2, where L is the length of S. If multiple rearrangements exist, return the one that comes earliest alphabetically. If there is no answer, print 'impossible.'

Input

The input contains the string S.

Output

Print 'impossible' if there is no answer. Otherwise, print a lexicographical first string that satisfies the given requirements.

Function

rearrangeString(s: String) → String

Examples

Example 1

s = "abca"return = "aabc"
No explanation is provided for now 😳🔫 As always, I will add it once find any. Or if you happen to know about it, feel free to dm Groot! Many thanks in advance! 🫶

Constraints

1 <= L <= 10^4

More Intuit problems

drafts saved locally
public String rearrangeString(String s) {
    // write your code here
}
s"abca"
expected"aabc"
checking account