# Smallest Palindromic Rearrangement I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/smallest-palindromic-rearrangement-i)
Canonical: https://scaleengineer.com/dsa/problems/smallest-palindromic-rearrangement-i
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Counting Sort](https://scaleengineer.com/algorithms/counting-sort)
**Data structures:** String
---
## Problem
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.

# Approaches
## Brute Force by Generating All Permutations
This is a naive approach that explores all possible rearrangements of the characters in the input string `s`. For each rearrangement (permutation), it checks if the new string is a palindrome. It keeps track of the lexicographically smallest palindrome found among all valid permutations.
**Time:** O(N * N!), where N is the length of the string. Generating all permutations is factorial in time, and for each permutation, we do an O(N) check. This is prohibitively slow. · **Space:** O(N), for the recursion stack depth and the `StringBuilder` used to build permutations.
**Pros:** It's a straightforward, brute-force method that correctly solves the problem for very small inputs.
**Cons:** Extremely inefficient and will not pass for the given constraints.; The number of permutations grows factorially with the length of the string, making it infeasible for `n > 15`.
### Explanation
The algorithm first needs a way to generate all unique permutations of the characters of `s`. This is typically done using a recursive backtracking function. The function would explore placing each available character at the current position in the permutation being built. To handle duplicate characters, we can use a frequency map of characters. Once a full permutation of length `n` is generated, we check if it's a palindrome. A string is a palindrome if it reads the same forwards and backwards. We maintain a variable, say `smallestPalindrome`, initialized to a lexicographically large value. Whenever we find a new palindrome, we compare it with `smallestPalindrome` and update it if the new one is smaller. After checking all possible permutations, `smallestPalindrome` will hold the answer. Given the constraints (`s.length <= 10^5`), this approach is computationally infeasible.

```java
// Note: This code is for demonstration and will cause a Time Limit Exceeded error.
class Solution {
    String smallestPalindrome = null;

    public String makeSmallestPalindrome(String s) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }
        generatePermutations(new StringBuilder(), counts, s.length());
        return smallestPalindrome;
    }

    private void generatePermutations(StringBuilder current, int[] counts, int n) {
        if (current.length() == n) {
            String perm = current.toString();
            if (isPalindrome(perm)) {
                if (smallestPalindrome == null || perm.compareTo(smallestPalindrome) < 0) {
                    smallestPalindrome = perm;
                }
            }
            return;
        }

        for (int i = 0; i < 26; i++) {
            if (counts[i] > 0) {
                counts[i]--;
                current.append((char) ('a' + i));
                generatePermutations(current, counts, n);
                // Backtrack
                current.deleteCharAt(current.length() - 1);
                counts[i]++;
            }
        }
    }

    private boolean isPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```
### Algorithm
- Count the frequency of each character in the input string `s`.
- Define a recursive backtracking function, `generate(current_permutation, character_counts)`.
- **Base Case:** If the length of `current_permutation` equals the length of `s`:
  - Check if `current_permutation` is a palindrome.
  - If it is, compare it with the smallest palindrome found so far and update if the current one is smaller.
  - Return.
- **Recursive Step:** Iterate through all possible characters ('a' to 'z').
  - If a character's count is greater than zero:
    - Decrement its count.
    - Append the character to `current_permutation`.
    - Make a recursive call: `generate(current_permutation, character_counts)`.
    - Backtrack: Remove the last character from `current_permutation` and restore the character's count.
- Initialize the process by calling the function with an empty permutation.
- The smallest palindrome found after exploring all possibilities is the answer.

## Greedy Approach with Character Counting
This approach leverages the properties of palindromes and lexicographical ordering. To form the lexicographically smallest palindrome, we must place the smallest characters at the beginning and end of the string, moving inwards. This can be achieved by constructing the first half of the palindrome to be the lexicographically smallest possible string that can be formed using half of the available characters.
**Time:** O(N), where N is the length of the string `s`. Counting characters takes O(N). Building the first half involves iterating 26 times, but the total number of appends is N/2, making it O(N). Reversing and building the final string are also O(N). · **Space:** O(N), where N is the length of `s`. We use an O(1) array for counts (size 26 is constant). However, the `StringBuilder` for the first half and the final result string both require O(N) space.
**Pros:** Optimal time complexity, solving the problem in a single pass after counting.; Relatively simple and easy to understand logic.; Guaranteed to find the correct answer due to the greedy choice of placing smallest characters first.
**Cons:** Requires extra space proportional to the input string length to build the result.
### Explanation
The core idea is to construct the first half of the palindrome first. This first half, when sorted, will result in the lexicographically smallest possible palindrome. We start by counting the frequency of each character in the input string `s`. An array of size 26 is sufficient for lowercase English letters. We then build the first half of the result. We iterate from 'a' to 'z'. For each character, we append it to our `firstHalf` builder `count / 2` times. This ensures the `firstHalf` is sorted. During this process, we can identify the single character that has an odd frequency (if one exists). This character will form the center of our final palindrome. Since the input is guaranteed to be a palindrome, there will be at most one such character. After constructing the `firstHalf`, we create the `secondHalf` by simply reversing the `firstHalf`. Finally, we concatenate the three parts: `firstHalf` + `middle_character` + `secondHalf`.

```java
class Solution {
    public String makeSmallestPalindrome(String s) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }

        StringBuilder firstHalf = new StringBuilder();
        String middleChar = "";

        for (int i = 0; i < 26; i++) {
            char c = (char) ('a' + i);
            int count = counts[i];
            
            for (int j = 0; j < count / 2; j++) {
                firstHalf.append(c);
            }
            
            if (count % 2 != 0) {
                middleChar = String.valueOf(c);
            }
        }

        String secondHalf = new StringBuilder(firstHalf).reverse().toString();
        
        return firstHalf.toString() + middleChar + secondHalf;
    }
}
```
### Algorithm
- Create an integer array `counts` of size 26, initialized to zeros, to store the frequency of each character.
- Iterate through the input string `s` and populate the `counts` array. `counts[c - 'a']++` for each character `c`.
- Initialize a `StringBuilder` called `firstHalf` and a `String` called `middleChar`.
- Iterate from `i = 0` to `25` (representing 'a' to 'z'):
  - Let `c` be the character `(char)('a' + i)`.
  - Append `c` to `firstHalf` `counts[i] / 2` times. This builds a sorted first half.
  - If `counts[i]` is odd, set `middleChar` to the string representation of `c`.
- Create a `String` `secondHalf` by reversing `firstHalf`.
- The result is the concatenation: `firstHalf.toString() + middleChar + secondHalf`.