3517. Smallest Palindromic Rearrangement I
Medium63.5% acceptance34,674 / 54,594 submissions
Asked by 2 companies
Topics
You are given a palindromic string s.
Return the lexicographically smallest palindromic permutation of s.
Example 1:
Input: s = "z"
Output: "z"
Explanation:
A string of only one character is already the lexicographically smallest palindrome.
Example 2:
Input: s = "babab"
Output: "abbba"
Explanation:
Rearranging "babab" → "abbba" gives the smallest lexicographic palindrome.
Example 3:
Input: s = "daccad"
Output: "acddca"
Explanation:
Rearranging "daccad" → "acddca" gives the smallest lexicographic palindrome.
Constraints:
1 <= s.length <= 105sconsists of lowercase English letters.sis guaranteed to be palindromic.
Hints
Hint 1
Consider a palindrome as composed of two mirror-image halves.
Hint 2
Construct one half (using
s), and then the other half is its reverse to obtain the lexicographically smallest permutation.