Palindrome Permutation - Practice Coding Problems

Palindrome Permutation - Problem

Given a string s, return true if a permutation of the string could form a palindrome and false otherwise.

A palindrome is a word that reads the same forward and backward (e.g., "racecar", "madam").

You need to determine if the characters in the string can be rearranged to form a palindrome, not whether the string itself is already a palindrome.

Example: The string "aab" can be rearranged to "aba", which is a palindrome, so the answer is true.

Input & Output

Example 1 — Can Form Palindrome

$ Input: s = "aab"

› Output: true

💡 Note: The string "aab" can be rearranged to "aba" which is a palindrome. Character 'a' appears 2 times (even), 'b' appears 1 time (odd). Since at most one character has odd frequency, a palindrome is possible.

Example 2 — Cannot Form Palindrome

$ Input: s = "carerac"

› Output: false

💡 Note: The string "carerac" has character frequencies: 'c'=2, 'a'=2, 'r'=2, 'e'=1. All characters appear an even number of times except 'e', but we cannot form a palindrome because the arrangement would be unbalanced.

Example 3 — Single Character

$ Input: s = "a"

› Output: true

💡 Note: A single character is always a palindrome. Character 'a' appears 1 time (odd), which is allowed.

Constraints

1 ≤ s.length ≤ 1000
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string with characters to analyze

Count Frequencies

Count how many times each character appears

Check Rule

At most one character can have odd count

Key Takeaway

🎯 Key Insight: A palindrome can have at most one character appearing an odd number of times (the middle character)

Asked in

G Google 25 f Facebook 30 a Amazon 20 M Microsoft 15

The key insight is that a palindrome can have at most one character with odd frequency (the middle character). The optimal approach uses frequency counting in O(n) time, or bit manipulation for O(1) space when dealing with limited character sets. Time: O(n), Space: O(k) where k is unique characters.

Common Approaches

Approach	Time	Space	Notes
✓ Generate All Permutations	O(n! × n)	O(n)	Generate all possible permutations and check if any forms a palindrome
Bit Manipulation Toggle	O(n)	O(1)	Use XOR to track odd character counts with a single integer
Character Frequency Count	O(n)	O(k)	Count character frequencies and check palindrome formation rules

Generate All Permutations — Algorithm Steps

Generate all permutations of the string
For each permutation, check if it's a palindrome
Return true if any palindrome is found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Create all possible arrangements

Check Each

Test if arrangement is palindrome

Return Result

Return true if any palindrome found

Code -

solution.c — C

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

bool isPalindrome(char* s) {
    int len = strlen(s);
    for (int i = 0; i < len / 2; i++) {
        if (s[i] != s[len - 1 - i]) {
            return false;
        }
    }
    return true;
}

void getPermutations(char* s, int start, int len, bool* found) {
    if (*found) return;
    if (start == len - 1) {
        if (isPalindrome(s)) {
            *found = true;
        }
        return;
    }
    
    for (int i = start; i < len; i++) {
        char temp = s[start];
        s[start] = s[i];
        s[i] = temp;
        
        getPermutations(s, start + 1, len, found);
        
        temp = s[start];
        s[start] = s[i];
        s[i] = temp;
    }
}

bool solution(char* s) {
    int len = strlen(s);
    char* copy = malloc((len + 1) * sizeof(char));
    strcpy(copy, s);
    
    bool found = false;
    getPermutations(copy, 0, len, &found);
    
    free(copy);
    return found;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    bool result = solution(s);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

n! permutations to generate, each taking O(n) time to check if palindrome

⚠ Quadratic Growth

Space Complexity

O(n)

Space to store each permutation and recursion stack

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~15 min Avg. Time

1.8K 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

Generate All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler