Palindrome Permutation II - Practice Coding Problems

Palindrome Permutation II - Problem

Given a string s, return all the palindromic permutations (without duplicates) of it.

You may return the answer in any order. If s has no palindromic permutation, return an empty list.

A palindromic permutation is a rearrangement of the string's characters that reads the same forwards and backwards.

Input & Output

Example 1 — Basic Case

$ Input: s = "aab"

› Output: ["aba"]

💡 Note: Character frequencies: a=2, b=1. Only one odd frequency (b), so palindrome possible. Arranging pairs 'a' around center 'b' gives 'aba'.

Example 2 — Multiple Palindromes

$ Input: s = "aabb"

› Output: ["abba", "baab"]

💡 Note: All characters have even frequencies. Can arrange pairs in 2 ways: 'a' pairs outside 'b' pairs gives 'abba', or 'b' pairs outside 'a' pairs gives 'baab'.

Example 3 — Impossible Case

$ Input: s = "abc"

› Output: []

💡 Note: All characters have frequency 1 (3 odd frequencies). Since more than 1 character has odd frequency, no palindromic permutation is possible.

Constraints

1 ≤ s.length ≤ 16
s contains only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Count character frequencies

Validation

Check if palindromes are possible

Generation

Build all unique palindromic arrangements

Key Takeaway

🎯 Key Insight: A palindrome can have at most one character with odd frequency - use this to validate early and build efficiently

Asked in

F Facebook 25 G Google 20 a Amazon 15

The key insight is that a palindrome can have at most one character with odd frequency. Best approach is optimized backtracking that builds palindromes directly by arranging character pairs around a center. Time: O(n × p!), Space: O(n) where p is the number of unique pairs.

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count + Validation	O(n × n!)	O(n)	Count character frequencies and validate palindrome possibility first
Generate All Permutations	O(n! × n)	O(n! × n)	Generate all permutations and filter palindromes
Optimized Backtracking	O(n × p!)	O(n)	Use backtracking to build palindromes directly from character pairs

Frequency Count + Validation — Algorithm Steps

Step 1: Count frequency of each character
Step 2: Check if palindrome is possible (≤ 1 odd frequency)
Step 3: If valid, generate palindromic permutations

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count each character occurrence

Validate Possibility

Check if palindrome can be formed

Build Palindromes

Generate valid arrangements

Code -

solution.c — C

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

int charCount[256];
char result[1000][20];
int resultCount = 0;

void backtrack(char* path, int pathLen, char* remaining, int remLen, char middle) {
    if (remLen == 0) {
        // Build palindrome
        char palindrome[20] = "";
        strncat(palindrome, path, pathLen);
        if (middle != ' ') {
            char mid[2] = {middle, '\0'};
            strcat(palindrome, mid);
        }
        // Reverse and append
        for (int i = pathLen - 1; i >= 0; i--) {
            char temp[2] = {path[i], '\0'};
            strcat(palindrome, temp);
        }
        
        // Check for duplicates
        for (int i = 0; i < resultCount; i++) {
            if (strcmp(result[i], palindrome) == 0) return;
        }
        strcpy(result[resultCount++], palindrome);
        return;
    }
    
    bool seen[256] = {false};
    for (int i = 0; i < remLen; i++) {
        if (seen[(unsigned char)remaining[i]]) continue;
        seen[(unsigned char)remaining[i]] = true;
        
        path[pathLen] = remaining[i];
        char newRemaining[20];
        int newLen = 0;
        for (int j = 0; j < remLen; j++) {
            if (j != i) {
                newRemaining[newLen++] = remaining[j];
            }
        }
        backtrack(path, pathLen + 1, newRemaining, newLen, middle);
    }
}

int main() {
    char s[20];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int len = strlen(s);
    if (len == 0) {
        printf("[]\n");
        return 0;
    }
    
    // Count frequencies
    memset(charCount, 0, sizeof(charCount));
    for (int i = 0; i < len; i++) {
        charCount[(unsigned char)s[i]]++;
    }
    
    // Check palindrome possibility
    int oddCount = 0;
    char middle = ' ';
    for (int i = 0; i < 256; i++) {
        if (charCount[i] % 2 == 1) {
            oddCount++;
            middle = (char)i;
        }
    }
    
    if (oddCount > 1) {
        printf("[]\n");
        return 0;
    }
    
    // Generate half characters
    char halfChars[20];
    int halfLen = 0;
    for (int i = 0; i < 256; i++) {
        int halfCount = charCount[i] / 2;
        for (int j = 0; j < halfCount; j++) {
            halfChars[halfLen++] = (char)i;
        }
    }
    
    char path[20];
    backtrack(path, 0, halfChars, halfLen, middle);
    
    printf("[");
    for (int i = 0; i < resultCount; i++) {
        printf("\"%s\"", result[i]);
        if (i < resultCount - 1) printf(",");
    }
    printf("]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × n!)

O(n) to count + validate, then O(n!) to generate valid permutations

⚠ Quadratic Growth

Space Complexity

O(n)

Hash map stores character frequencies

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 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 + Validation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler