237. Palindrome Permutation
You are given a string s of lowercase English letters. Decide whether the letters of s can be rearranged into a palindrome — a string that reads identically forwards and backwards. Return true if some rearrangement works, false if none does.
You never need to build the palindrome itself. A palindrome pairs every character with its mirror, so the question reduces to a property of the letter counts: how many letters are allowed to appear an odd number of times?
Example 1:
Input: s = "vicci"
Output: true
Explanation: The letters can be rearranged into "civic". Counts: c×2, i×2, v×1 — only one letter (v) has an odd count, and it can sit in the middle.
Example 2:
Input: s = "code"
Output: false
Explanation: Counts: c×1, o×1, d×1, e×1 — four letters occur an odd number of times, but a palindrome has room for at most one unpaired letter.
Example 3:
Input: s = "aab"
Output: true
Explanation: "aba" is a palindrome using exactly these letters.
Constraints:
- 1 ≤ s.length ≤ 5000
- s consists of lowercase English letters only.
Hints:
In a palindrome, position i mirrors position length−1−i, so characters come in pairs — except possibly one lone character in the exact middle of an odd-length string.
So count each letter: a rearrangement into a palindrome exists exactly when at most one letter has an odd count. You don't even need to distinguish even from odd lengths — the counts settle it.
You only care about count *parity*, not the counts themselves. Toggle one bit per letter in a 26-bit mask; at the end the answer is whether the mask has at most one set bit — `mask & (mask - 1) == 0` checks that in O(1).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "vicci"
Expected output: true