Lexicographically Smallest Palindrome Possible 🍊
MediumAsked in:Amazon•Stage:Online Assessment
stringtwo_pointersgreedy
Problem Statement
Given a string S of length n, rearrange its characters to form a palindrome. If multiple palindromes are possible, output the lexicographically smallest one. If it is impossible to form any palindrome, output "-1".
Input Format
A single line containing the string S (1 ≤ |S| ≤ 10^5), consisting of lowercase English letters.
Output Format
Print the lexicographically smallest palindrome that can be formed from S, or "-1" if no palindrome exists.
Constraints
- 1 <= n <= 10^5
- S contains only lowercase English letters