Rearrange String

Problem Statement

Rearrange String Problem Description 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 , 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. Examples Example 1: Input: abca Output: aabc Explanation: We need to move the second 'a' at the beginning of the string so that S[0] != S[3] , S[1] != S[2] , and 'aabc' are the alphabetically smallest string among all valid answers. Example 2: Input: abaa Output: impossible Explanation: There is no way to rearrange the characters of the given string in the required manner. Constraints 1