Practice/Meta/Leetcode 266. Palindrome Permutation

Leetcode 266. Palindrome Permutation

CodingOptional

Problem

Given a string, determine whether its characters can be rearranged to form a palindrome. You don't need to construct the palindrome itself—just return whether it's possible to create one by reordering the characters.

A palindrome reads the same forwards and backwards. For a string's characters to form a palindrome, the character frequencies must follow specific rules based on whether the resulting palindrome would have even or odd length.

Requirements

1. Return true if any permutation of the input string can form a palindrome
2. Return false if no valid palindrome arrangement exists
3. Handle empty strings and single characters appropriately
4. Consider only the characters themselves, not their original positions

Constraints

• 0 ≤ s.length ≤ 5000
• The string consists of printable ASCII characters
• Time complexity should be O(n) where n is the length of the string
• Space complexity should be O(k) where k is the number of unique characters

Examples

Example 1:

Input: s = "aabb" Output: true Explanation: The characters can be rearranged to form "abba" or "baab", both valid palindromes.

Example 2:

Input: s = "carerac" Output: true Explanation: Can be rearranged to "racecar". The letter 'e' appears once (odd), 'c' twice, 'a' twice, 'r' twice.

Example 3:

Input: s = "code" Output: false Explanation: Each character appears exactly once. We would need at least 3 characters to have matching pairs.

Example 4:

Input: s = "a" Output: true Explanation: A single character is itself a palindrome.