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 step-by-step:

  1. Count Characters: Counter(s) creates a dictionary-like object where keys are the characters from the string s, and values are the counts of these characters. For example, if s = "aabb", Counter(s) would produce Counter({'a': 2, 'b': 2}).

  2. Check Character Counts: The expression v % 2 computes the remainder when each character count v 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).

  3. Sum of Odd Counts: The generator expression v % 2 for v in Counter(s).values() produces a sequence of 0s and 1s, representing even and odd counts, respectively. The sum(...) function adds up these values, yielding the total number of characters that occur an odd number of times in the string.

  4. 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 string s 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 odd-count 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 rearrange s into a palindrome.

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;
};

All Problems

All Solutions