LeetCode 3517: Smallest Palindromic Rearrangement I Solution

Master LeetCode problem 3517 (Smallest Palindromic Rearrangement I), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3517. Smallest Palindromic Rearrangement I

Medium

String Sorting Counting Sort

Problem Explanation

Explanation

To find the lexicographically smallest palindromic permutation of a given palindromic string s, we can follow these steps:

Count the frequency of each character in the string.
Construct the first half of the palindrome by adding characters in non-decreasing order of their ASCII values.
If the length of the string is odd, append the character with the highest frequency in the middle. Otherwise, there is no need to add a middle character.
Construct the second half of the palindrome by adding characters in non-increasing order of their ASCII values.
Assemble the first and second halves to form the final palindrome.

The time complexity of this algorithm is O(n) where n is the length of the input string s, as we iterate over the string to count frequencies and construct the palindrome. The space complexity is also O(n) to store the frequency counts.

Solution Code

import java.util.Arrays;

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

        char[] res = new char[s.length()];
        int left = 0, right = s.length() - 1;

        for (int i = 0; i < 26; i++) {
            char ch = (char)('a' + i);
            while (count[i] > 1) {
                res[left++] = ch;
                res[right--] = ch;
                count[i] -= 2;
            }
        }

        for (int i = 0; i < 26; i++) {
            char ch = (char)('a' + i);
            if (count[i] == 1) {
                res[s.length() / 2] = ch;
                count[i]--;
                break;
            }
        }

        return new String(res);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3517 (Smallest Palindromic Rearrangement I)?

This page provides optimized solutions for LeetCode problem 3517 (Smallest Palindromic Rearrangement I) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3517 (Smallest Palindromic Rearrangement I)?

The time complexity for LeetCode 3517 (Smallest Palindromic Rearrangement I) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3517 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3517 in Java, C++, or Python.

Back to LeetCode Solutions