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 <= 5000sconsists of only lowercase English letters.
Solutions
Solution 1: Counting
If a string is a palindrome, at most one character can appear an odd number of times, while all other characters must appear an even number of times. Therefore, we only need to count the occurrences of each character and then check if this condition is satisfied.
Time complexity is $O(n)$, and space complexity is $O(|\Sigma|)$. Here, $n$ is the length of the string, and $|\Sigma|$ is the size of the character set. In this problem, the character set consists of lowercase letters, so $|\Sigma|=26$.
Python3
class Solution:
def canPermutePalindrome(self, s: str) -> bool:
return sum(v & 1 for v in Counter(s).values()) < 2
Java
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;
}
}
C++
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;
}
};
Go
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
}
TypeScript
function canPermutePalindrome(s: string): boolean {
const cnt: number[] = Array(26).fill(0);
for (const c of s) {
++cnt[c.charCodeAt(0) - 97];
}
return cnt.filter(c => c % 2 === 1).length < 2;
}
JavaScript
/**
* @param {string} s
* @return {boolean}
*/
var canPermutePalindrome = function (s) {
const cnt = new Map();
for (const c of s) {
cnt.set(c, (cnt.get(c) || 0) + 1);
}
return [...cnt.values()].filter(v => v % 2 === 1).length < 2;
};