3517. Smallest Palindromic Rearrangement I LeetCode Solution

Last updated: April 22, 2025

In this guide, you will get 3517. Smallest Palindromic Rearrangement I LeetCode Solution with the best time and space complexity. The solution to Smallest Palindromic Rearrangement I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Smallest Palindromic Rearrangement I solution in C++
Smallest Palindromic Rearrangement I solution in Java
Smallest Palindromic Rearrangement I solution in Python
Additional Resources

3517. Smallest Palindromic Rearrangement I LeetCode Solution image

Problem Statement of Smallest Palindromic Rearrangement I

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 <= 105
s consists of lowercase English letters.
s is guaranteed to be palindromic.

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(n)

3517. Smallest Palindromic Rearrangement I LeetCode Solution in C++

class Solution {
 public:
  string smallestPalindrome(string s) {
    const int n = s.length();
    const string sortedHalf = getSortedHalf(s);
    return sortedHalf + (n % 2 ? string(1, s[n / 2]) : "") +
           reversed(sortedHalf);
  }

 private:
  string getSortedHalf(const string& s) {
    string half = s.substr(0, s.length() / 2);
    ranges::sort(half);
    return half;
  }

  string reversed(const string& s) {
    return {s.rbegin(), s.rend()};
  }
};
/* code provided by PROGIEZ */

3517. Smallest Palindromic Rearrangement I LeetCode Solution in Java

class Solution {
  public String smallestPalindrome(String s) {
    final int n = s.length();
    final String sortedHalf = getSortedHalf(s);
    return sortedHalf + (n % 2 == 1 ? String.valueOf(s.charAt(n / 2)) : "") + reversed(sortedHalf);
  }

  private String getSortedHalf(final String s) {
    final String half = s.substring(0, s.length() / 2);
    char[] chars = half.toCharArray();
    Arrays.sort(chars);
    return new String(chars);
  }

  private String reversed(final String s) {
    return new StringBuilder(s).reverse().toString();
  }
}
// code provided by PROGIEZ

3517. Smallest Palindromic Rearrangement I LeetCode Solution in Python

class Solution:
  def smallestPalindrome(self, s: str) -> str:
    n = len(s)
    sortedHalf = sorted(s[:n // 2])
    return ''.join(sortedHalf +
                   ([s[n // 2]] if n % 2 else []) +
                   sortedHalf[::-1])
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents