We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Palindrome Permutation

Number: 266

Difficulty: Easy

Paid? Yes

Companies: Meta, Apple, Microsoft, Nordstrom, Google, Uber, Bloomberg

Problem Description

Given a string s, determine if any permutation of the string can form a palindrome. Return true if a palindrome permutation exists, and false otherwise.

Key Insights

  • A string can form a palindrome if at most one character appears an odd number of times.
  • Use a hash table (or frequency array) to count occurrences of each character.
  • For bit manipulation, toggle bits for each character and ensure the final bitmask has at most one bit set.
  • The problem does not require generating the permutation, just checking the possibility.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1) since at most 26 characters are stored in the hash table.

Solution

We count the frequency of each character in the string. In a valid palindrome permutation, no more than one character can have an odd frequency (this would be the middle element in an odd-length palindrome). We iterate through the character frequencies, and if more than one character appears an odd number of times, we return false; otherwise, we return true. This approach uses a hash table for counting and is efficient given the constraints.

Code Solutions

# Python solution

def canPermutePalindrome(s):
    # Initialize dictionary to count character frequencies
    char_count = {}
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1

    # Variable to keep track of odd frequency occurrences
    odd_count = 0
    for count in char_count.values():
        if count % 2 != 0:
            odd_count += 1
            # More than one odd count means palindrome permutation is not possible
            if odd_count > 1:
                return False
    return True

# Example usage:
print(canPermutePalindrome("code"))    # Expected output: False
print(canPermutePalindrome("aab"))     # Expected output: True
print(canPermutePalindrome("carerac")) # Expected output: True
← Back to All Questions