Smallest Palindromic Rearrangement I - Practice Coding Problems

Smallest Palindromic Rearrangement I - Problem

You are given a palindromic string s. Return the lexicographically smallest palindromic permutation of s.

A palindromic string reads the same forward and backward. A lexicographically smaller string is one that would appear earlier in dictionary order.

Since the input is already a palindrome, we need to find the smallest possible rearrangement that maintains the palindromic property.

Input & Output

Example 1 — Basic Rearrangement

$ Input: s = "aabcc"

› Output: "acbca"

💡 Note: The input "aabcc" can be rearranged to form "acbca" which is a palindrome. This is the lexicographically smallest palindromic permutation possible.

Example 2 — Already Optimal

$ Input: s = "abc"

› Output: "abc"

💡 Note: The string "abc" is already a palindrome and in its lexicographically smallest form, so we return it as is.

Example 3 — Single Character

$ Input: s = "a"

› Output: "a"

💡 Note: A single character is always a palindrome and is already in its smallest form.

Constraints

1 ≤ s.length ≤ 1000
s consists of lowercase English letters
s is guaranteed to be a palindrome

Visualization

Tap to expand

Understanding the Visualization

Input

Given palindromic string with characters to rearrange

Process

Sort characters and build palindrome symmetrically

Output

Lexicographically smallest palindromic permutation

Key Takeaway

🎯 Key Insight: Sort all characters first, then build the palindrome symmetrically to guarantee the lexicographically smallest result

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that to get the lexicographically smallest palindrome, we should sort all characters and place them symmetrically from outside to center. The optimal approach sorts the string and constructs the palindrome in one pass. Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count and Construction	O(n log n)	O(k)	Count character frequencies and construct palindrome systematically
Brute Force - Generate All Permutations	O(n!×n)	O(n!)	Generate all possible permutations and find the smallest palindrome
Sort and Build Optimally	O(n log n)	O(1)	Sort characters and construct palindrome in one pass for optimal result

Frequency Count and Construction — Algorithm Steps

Count frequency of each character
Build first half by placing characters in sorted order
Handle middle character if string length is odd
Mirror first half to create the complete palindrome

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count each character occurrence

Build First Half

Place half of each character count

Mirror and Complete

Add middle char and mirror first half

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return *(char*)a - *(char*)b;
}

char* solution(char* s) {
    int len = strlen(s);
    int freq[256] = {0};
    
    // Count frequency of each character
    for (int i = 0; i < len; i++) {
        freq[(int)s[i]]++;
    }
    
    // Collect characters and sort them
    char chars[256];
    int charCount = 0;
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            chars[charCount++] = (char)i;
        }
    }
    qsort(chars, charCount, sizeof(char), compare);
    
    // Build result
    char* result = malloc(len + 1);
    int pos = 0;
    char middle = 0;
    
    // Build first half
    for (int i = 0; i < charCount; i++) {
        char c = chars[i];
        int count = freq[(int)c];
        // Add half of the characters to first half
        for (int j = 0; j < count / 2; j++) {
            result[pos++] = c;
        }
        // If odd count, this character can be in middle
        if (count % 2 == 1) {
            middle = c;
        }
    }
    
    // Add middle character if any
    int midPos = pos;
    if (middle != 0) {
        result[pos++] = middle;
    }
    
    // Mirror first half
    for (int i = midPos - 1; i >= 0; i--) {
        result[pos++] = result[i];
    }
    
    result[pos] = '\0';
    return result;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Counting takes O(n), sorting characters takes O(k log k) where k ≤ 26, building result takes O(n)

⚡ Linearithmic

Space Complexity

O(k)

Hash map stores at most k distinct characters where k ≤ 26 for lowercase letters

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count and Construction — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler