💬 Discord
Sign In
NeetCode #15LC-266EasyArrays & HashingNC Algo100
← Back to All Problems

#15 · #266 · Palindrome Permutation(回文排列)

📌 Problem Statement & Constraints

Given a string s, return true if a permutation of s could form a palindrome. Constraints: 1 <= s.length <= 5000; s consists of lowercase English letters.

💡 Core Algorithmic Approaches

  1. A string can be rearranged into a palindrome exactly when at most one character has an odd frequency: the palindrome's mirror pairs consume characters two at a time, leaving at most one unpaired centre character.
  2. Count the frequencies, then count how many are odd.
  3. Return whether that count is at most 1.
  4. Equivalently, use a bitmask and check that at most one bit is set -- a neat O(1)-space variant.

💻 Benchmark Python3 Implementation

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        from collections import Counter
        return sum(v % 2 for v in Counter(s).values()) <= 1


# Bitmask variant: parity of each letter tracked as one bit
class Solution2:
    def canPermutePalindrome(self, s: str) -> bool:
        mask = 0
        for ch in s:
            mask ^= 1 << (ord(ch) - 97)    # XOR toggles the parity bit
        return mask & (mask - 1) == 0      # at most one bit set

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass to count, plus a constant-size scan over the 26 letters.
💾 Space Complexity
O(1): the counter holds at most 26 entries, and the bitmask variant uses a single integer.

⚠️ Interview Pitfalls & Follow-ups

  • Requiring zero odd counts: an odd-length palindrome always has exactly one odd-count character, so the threshold is <= 1, not == 0.
  • Checking whether s is already a palindrome: the question is about any permutation, not the given order.
  • Trying to enumerate permutations: factorial time for no reason.