Palindrome Permutation

XXX. Can Permute Palindrome

Hashing

Set Operations

Problem Statement:

Given a string s, determine if a permutation of the string can form a palindrome. A string is a palindrome if it reads the same backward as forward.

Algorithm:

1. Use a Set to track characters with odd frequencies.
2. Iterate through the characters of the string:
   • If a character is not in the Set, add it.
   • If a character is already in the Set, remove it.
3. At the end:
   • If the size of the Set is 0 or 1, the string can be permuted into a palindrome.
   • Otherwise, it cannot.

Complexity:

Time Complexity: O(n), where n is the length of the string. We iterate through the string once.
Space Complexity: O(1), as the Set contains at most 26 characters (for the English alphabet).

Java Implementation:

public boolean canPermutePalindrome(String s) {
    Set set = new HashSet<>(); // Set to track odd frequency characters
    for (int i = 0; i < s.length(); ++i) {
        char c = s.charAt(i);
        // Toggle character in the set
        if (!set.contains(c)) 
            set.add(c);
        else 
            set.remove(c);
    }
    // A palindrome permutation is valid if there's at most one odd frequency character
    return set.size() == 0 || set.size() == 1;
}
                

Python Implementation:

def canPermutePalindrome(s):
    # Set to track characters with odd frequencies
    char_set = set()
    for char in s:
        # Toggle character in the set
        if char not in char_set:
            char_set.add(char)
        else:
            char_set.remove(char)
    # A palindrome permutation is valid if there's at most one odd frequency character
    return len(char_set) <= 1
                

C++ Implementation:

bool canPermutePalindrome(string s) {
    unordered_set charSet; // Set to track odd frequency characters
    for (char c : s) {
        // Toggle character in the set
        if (charSet.count(c)) 
            charSet.erase(c);
        else 
            charSet.insert(c);
    }
    // A palindrome permutation is valid if there's at most one odd frequency character
    return charSet.size() <= 1;
}