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
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$.
1 2 3 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|