Rearrange String

Problem Overview

• Rearrange characters of a string S so that for every i with 0 <= i < (L - 1) / 2, S[i] != S[L - i - 1].
• Input is a string S; output the lexicographically earliest valid rearrangement or 'impossible' if none exists.
• Constraint: length L is between 1 and 10^4.
• This string manipulation interview question from Intuit interviews tests reasoning about symmetric pairs and ordering, common in a coding interview problem.