Palindrome Permutation

XXX. Palindrome Permutation

Hash Set

Backtracking

String

Problem Statement:

Given a string s, determine whether any permutation of the string is a palindrome. Additionally, generate all possible palindrome permutations of the string if they exist.

Algorithm:

Checking Palindrome Permutation:

1. Use a Set to track characters with odd frequencies.
2. Iterate through the string and add or remove characters from the Set based on their presence.
3. If the size of the Set is 0 or 1, the string can form a palindrome permutation.

Generating Palindrome Permutations:

1. Count the frequency of each character using a Map.
2. Check if the string can form a palindrome permutation by validating the character counts.
3. Split the characters into halves for constructing the palindrome.
4. Use backtracking to generate permutations of the first half.
5. Construct full palindromes by mirroring the generated half and adding a middle character if necessary.

Complexity:

Time Complexity:

• Checking palindrome permutation: O(n), where n is the length of the string.
• Generating permutations: O((n/2)!), where n/2 is the length of half the string.

Space Complexity: O(n) for storing character counts and intermediate results.

Java Implementation:

// Checking if a permutation can form a palindrome
public boolean canPermutePalindrome(String s) {
    Set set = new HashSet<>();
    for (char c : s.toCharArray()) {
        if (!set.add(c)) set.remove(c);
    }
    return set.size() <= 1;
}

// Generating all palindrome permutations
public List generatePalindromes(String s) {
    List result = new ArrayList<>();
    Map count = new HashMap<>();

    for (char c : s.toCharArray()) count.put(c, count.getOrDefault(c, 0) + 1);

    if (!canPermutePalindrome(s)) return result;

    char oddChar = 0;
    for (Map.Entry entry : count.entrySet()) {
        if (entry.getValue() % 2 != 0) oddChar = entry.getKey();
        count.put(entry.getKey(), entry.getValue() / 2);
    }

    permute(result, new StringBuilder(), count, s.length() / 2, oddChar);
    return result;
}

private void permute(List result, StringBuilder prefix, Map count, int length, char oddChar) {
    if (prefix.length() == length) {
        StringBuilder reverse = new StringBuilder(prefix).reverse();
        if (oddChar != 0) prefix.append(oddChar);
        prefix.append(reverse);
        result.add(prefix.toString());
        if (oddChar != 0) prefix.deleteCharAt(length);
        prefix.setLength(length);
        return;
    }

    for (char c : count.keySet()) {
        if (count.get(c) > 0) {
            count.put(c, count.get(c) - 1);
            prefix.append(c);
            permute(result, prefix, count, length, oddChar);
            prefix.deleteCharAt(prefix.length() - 1);
            count.put(c, count.get(c) + 1);
        }
    }
}
                

Python Implementation:

def can_permute_palindrome(s: str) -> bool:
    from collections import Counter
    count = Counter(s)
    return sum(v % 2 for v in count.values()) <= 1

def generate_palindromes(s: str) -> list:
    from collections import Counter

    count = Counter(s)
    if sum(v % 2 for v in count.values()) > 1:
        return []

    odd_char = ""
    for char, freq in count.items():
        if freq % 2:
            odd_char = char
        count[char] //= 2

    def backtrack(path):
        if len(path) == len(s) // 2:
            result.append("".join(path + [odd_char] + path[::-1]))
            return
        for char in count:
            if count[char] > 0:
                count[char] -= 1
                path.append(char)
                backtrack(path)
                path.pop()
                count[char] += 1

    result = []
    backtrack([])
    return result
                

C++ Implementation:

#include 
#include 
#include 
#include 
using namespace std;

bool canPermutePalindrome(string s) {
    unordered_map count;
    for (char c : s) count[c]++;
    int odd = 0;
    for (auto [_, freq] : count)
        if (freq % 2) odd++;
    return odd <= 1;
}

vector generatePalindromes(string s) {
    unordered_map count;
    for (char c : s) count[c]++;
    int odd = 0;
    char odd_char = 0;
    for (auto [c, freq] : count)
        if (freq % 2) {
            odd++;
            odd_char = c;
        }
    if (odd > 1) return {};

    string half;
    for (auto [c, freq] : count)
        half += string(freq / 2, c);

    vector result;
    sort(half.begin(), half.end());
    do {
        string pal = half;
        if (odd_char) pal += odd_char;
        pal += string(half.rbegin(), half.rend());
        result.push_back(pal);
    } while (next_permutation(half.begin(), half.end()));

    return result;
}