Welcome to Subscribe On Youtube
266. Palindrome Permutation
Description
Given a string s
, return true
if a permutation of the string could form a palindrome and false
otherwise.
Example 1:
Input: s = "code" Output: false
Example 2:
Input: s = "aab" Output: true
Example 3:
Input: s = "carerac" Output: true
Constraints:
1 <= s.length <= 5000
s
consists of only lowercase English letters.
Solutions
Core Logic:
The code employs a concise strategy using Python’s Counter
class from the collections
module to count the occurrences of each character in the string. It then checks the parity (even or odd) of the counts of all characters. Here’s how it works stepbystep:

Count Characters:
Counter(s)
creates a dictionarylike object where keys are the characters from the strings
, and values are the counts of these characters. For example, ifs = "aabb"
,Counter(s)
would produceCounter({'a': 2, 'b': 2})
. 
Check Character Counts: The expression
v % 2
computes the remainder when each character countv
is divided by 2. This operation effectively checks whether each count is even or odd. In a palindrome, most characters must occur an even number of times so that they can be mirrored around the center. However, for palindromes of odd length, one character can occur an odd number of times (as the central character). 
Sum of Odd Counts: The generator expression
v % 2 for v in Counter(s).values()
produces a sequence of0
s and1
s, representing even and odd counts, respectively. Thesum(...)
function adds up these values, yielding the total number of characters that occur an odd number of times in the string. 
Palindromic Permutation Check: The condition
sum(v % 2 for v in Counter(s).values()) <= 1
checks whether there is at most one character that occurs an odd number of times. This is a necessary and sufficient condition for the strings
to be rearrangeable into a palindrome: If all characters occur an even number of times (
sum(...) == 0
),s
can be arranged into a palindrome where characters are mirrored around the center.  If exactly one character occurs an odd number of times (
sum(...) == 1
),s
can be arranged into a palindrome with the oddcount character in the center and all other characters mirrored around it.  If more than one character occurs an odd number of times (
sum(...) > 1
), it is impossible to rearranges
into a palindrome.
 If all characters occur an even number of times (
Example:
For s = "carerac"
, Counter(s)
produces Counter({'c': 2, 'a': 2, 'r': 2, 'e': 1})
. The sum of odd counts is 1
(since only ‘e’ occurs an odd number of times), satisfying the condition for being rearrangeable into a palindrome.
Hence, the method canPermutePalindrome
returns True
if it’s possible to rearrange the input string s
into a palindrome based on the counts of its characters, and False
otherwise.

class Solution { public boolean canPermutePalindrome(String s) { int[] cnt = new int[26]; for (char c : s.toCharArray()) { ++cnt[c  'a']; } int odd = 0; for (int x : cnt) { odd += x & 1; } return odd < 2; } }

class Solution { public: bool canPermutePalindrome(string s) { vector<int> cnt(26); for (char& c : s) { ++cnt[c  'a']; } int odd = 0; for (int x : cnt) { odd += x & 1; } return odd < 2; } };

class Solution: def canPermutePalindrome(self, s: str) > bool: return sum(v % 2 for v in Counter(s).values()) <= 1 ############ class Solution(object): def canPermutePalindrome(self, s): """ :type s: str :rtype: bool """ oddChars = set() for c in s: if c in oddChars: oddChars.remove(c) else: oddChars.add(c) return len(oddChars) <= 1

func canPermutePalindrome(s string) bool { cnt := [26]int{} for _, c := range s { cnt[c'a']++ } odd := 0 for _, x := range cnt { odd += x & 1 } return odd < 2 }

function canPermutePalindrome(s: string): boolean { const cnt: number[] = new Array(26).fill(0); for (const c of s) { ++cnt[c.charCodeAt(0)  97]; } return cnt.filter(c => c % 2 === 1).length < 2; }

/** * @param {string} s * @return {boolean} */ var canPermutePalindrome = function (s) { const cnt = new Array(26).fill(0); for (const c of s) { ++cnt[c.charCodeAt()  'a'.charCodeAt()]; } return cnt.filter(c => c % 2 === 1).length < 2; };