Smallest Palindromic Rearrangement I

• 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.

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.

1// Note: This code is for demonstration and will cause a Time Limit Exceeded error.2class Solution {3    String smallestPalindrome = null;4 5    public String makeSmallestPalindrome(String s) {6        int[] counts = new int[26];7        for (char c : s.toCharArray()) {8            counts[c - 'a']++;9        }10        generatePermutations(new StringBuilder(), counts, s.length());11        return smallestPalindrome;12    }13 14    private void generatePermutations(StringBuilder current, int[] counts, int n) {15        if (current.length() == n) {16            String perm = current.toString();17            if (isPalindrome(perm)) {18                if (smallestPalindrome == null || perm.compareTo(smallestPalindrome) < 0) {19                    smallestPalindrome = perm;20                }21            }22            return;23        }24 25        for (int i = 0; i < 26; i++) {26            if (counts[i] > 0) {27                counts[i]--;28                current.append((char) ('a' + i));29                generatePermutations(current, counts, n);30                // Backtrack31                current.deleteCharAt(current.length() - 1);32                counts[i]++;33            }34        }35    }36 37    private boolean isPalindrome(String str) {38        int left = 0;39        int right = str.length() - 1;40        while (left < right) {41            if (str.charAt(left) != str.charAt(right)) {42                return false;43            }44            left++;45            right--;46        }47        return true;48    }49}

• 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.

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.

1class Solution {2    public String makeSmallestPalindrome(String s) {3        int[] counts = new int[26];4        for (char c : s.toCharArray()) {5            counts[c - 'a']++;6        }7 8        StringBuilder firstHalf = new StringBuilder();9        String middleChar = "";10 11        for (int i = 0; i < 26; i++) {12            char c = (char) ('a' + i);13            int count = counts[i];14            15            for (int j = 0; j < count / 2; j++) {16                firstHalf.append(c);17            }18            19            if (count % 2 != 0) {20                middleChar = String.valueOf(c);21            }22        }23 24        String secondHalf = new StringBuilder(firstHalf).reverse().toString();25        26        return firstHalf.toString() + middleChar + secondHalf;27    }28}