Palindrome Permutation solution and explanation
Google
9 more videos on this problem
LeetCode 266. Palindrome Permutation (Algorithm Explained)Nick White · 5:53 · 22K views
LeetCode 266. Palindrome Permutation | JSer - JavaScript & AlgorithmJSer · 4:40 · 483 views
Palindrome Permutation | Facebook Question | LeetCode 266Manny Rain · 16:14 · 462 views
LeetCode Q 266. Palindrome PermutationSweet AI · 4:16 · 372 views
Microsoft Coding Interview Question | Leetcode 266 | Palindrome PermutationWorkWithGoogler · 4:10 · 286 views
Palindrome Permutation LeetCode - JavaCode with Katie · 6:18 · 242 views
266. Palindrome Permutation - English VersionSimple Code - 단순코드 · 6:36 · 232 views
266. Palindrome Permutation - Week 3/5 Leetcode March ChallengeProgramming Live with Larry · 2:48 · 194 views
Leetcode 266 Palindrome PermutationAlgorithmicIQ · 10:12 · 181 views
Leetcode | 266. Palindrome Permutation | Easy | JavascriptSoftware Interviews Prep · 9:55 · 117 views
The problem
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.
Approach overview
Problem Overview: Given a string s, determine whether any permutation of its characters can form a palindrome. A palindrome reads the same forward and backward, which imposes strict constraints on character frequencies.
A key observation: in a valid palindrome, every character must appear an even number of times except possibly one character in the center. That means the string can contain at most one character with an odd frequency.
Approach 1: Counting with Hash Table (O(n) time, O(1) space)
Count how many times each character appears using a hash table. Iterate through the string once and update the count for each character. After building the frequency map, iterate over the counts and track how many characters have odd frequencies.
If more than one character has an odd count, forming a palindrome is impossible. Otherwise, at least one permutation exists that arranges the characters symmetrically. The algorithm performs a single pass for counting and another small pass over the frequency map, resulting in O(n) time. Space is O(1) because the character set is bounded (for example ASCII).
This approach is straightforward and reliable. It demonstrates clear understanding of the palindrome property and uses constant-time lookups from a hash map. Problems involving character frequency analysis often use the same pattern across many string problems.
Approach 2: Bit Manipulation Toggle (O(n) time, O(1) space)
A more compact solution tracks odd/even counts using a bitmask. Instead of storing counts, toggle a bit corresponding to each character as you iterate through the string. If a character appears twice, its bit flips twice and returns to zero. At the end, the bitmask contains bits set only for characters with odd frequency.
A string can form a palindrome if the bitmask has either zero bits set or exactly one bit set. This can be checked using the expression mask & (mask - 1), which removes the lowest set bit. If the result is zero, at most one bit was set.
This technique reduces memory overhead and showcases efficient bit manipulation. It is particularly useful when the character set is small (like lowercase English letters).
Recommended for interviews: The hash table counting approach is what most interviewers expect first because it clearly communicates the palindrome frequency rule and runs in O(n) time with constant space. Mentioning the bitmask optimization afterward shows deeper understanding and comfort with low-level operations. Starting with counting proves correctness; following up with bit manipulation demonstrates strong problem-solving range.
Solution
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.
class Solution:
def canPermutePalindrome(self, s: str) -> bool:
return sum(v & 1 for v in Counter(s).values()) < 2class 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;
}
};/**
* @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;
};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;
}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
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Table Character Counting | O(n) | O(1) | General solution. Clear logic and easiest to explain during interviews. |
| Bit Manipulation Toggle Mask | O(n) | O(1) | When character set is small and you want a compact, optimized solution. |
Frequently asked questions
Is Palindrome Permutation easy or hard?
Palindrome Permutation is classified as an Easy problem. The core idea relies on a simple observation about palindrome character frequencies, making it a common early interview question for practicing hash table and string manipulation concepts.
Palindrome Permutation Python/Java solution
In Python or Java, iterate through the string and maintain a frequency map using a dictionary or HashMap. After counting characters, verify that at most one character has an odd count. This approach is concise, readable, and runs in O(n) time.
How to solve Palindrome Permutation in O(n)?
Iterate through the string and count occurrences of each character using a hash map or array. After counting, check how many characters have odd frequencies. If the number of odd counts is greater than one, a palindrome permutation is impossible; otherwise it is valid.
What is the best approach for Palindrome Permutation?
The best approach uses a hash table to count character frequencies. A string can form a palindrome if at most one character has an odd frequency. This method runs in O(n) time and O(1) space since the character set is bounded.
Is Palindrome Permutation asked at Google/Amazon/Meta?
Palindrome Permutation is a classic string and hash table interview question. Variants of this problem frequently appear in interviews at companies like Amazon, Google, and Meta because it tests understanding of character frequency patterns and basic data structures.
What data structure is used in Palindrome Permutation?
The most common data structure is a hash table (or fixed-size array) to track character frequencies. Some optimized solutions use a bitmask to toggle bits representing characters, which relies on bit manipulation instead of storing explicit counts.
What is the time complexity of Palindrome Permutation?
The optimal solution runs in O(n) time where n is the length of the string. You scan the string once to count characters and then check the number of odd frequencies. Space complexity is O(1) because only a fixed-size frequency structure is required.