266. Palindrome Permutation

EasyBit ManipulationHash TableString

Problem Description

The problem asks to determine whether a permutation of the given string s can form a palindrome. A palindrome is a word, phrase, number, or other sequences of characters which reads the same forward and backward (ignoring spaces, punctuation, and capitalization). For a string to have a palindromic permutation, it must satisfy certain conditions based on the count of each character. Specifically:

If the length of the string is even, every character must appear an even number of times.
If the length of the string is odd, only one character can appear an odd number of times, while all others must appear an even number of times.

The goal is to return true if at least one permutation of the string could potentially be a palindrome. Otherwise, the function should return false.

Intuition

A palindrome has a characteristic symmetry. For strings of even length, this means that each character must have a matching pair. For strings of odd length, there can be one unique character (without a pair), but all other characters must still have matching pairs.

The intuition behind the solution is based on this observation. We can count the frequency of each character in the string using Python's Counter class from the collections module, which will give us a dictionary where the keys are the characters and the values are the counts. We then check the parity (even or odd) of these counts.

In the solution, the expression v & 1 will give 1 for odd counts and 0 for even counts of characters, because the bitwise AND operation with 1 will check the least significant bit of the count (odd numbers have a least significant bit of 1).

By summing these up, we're effectively counting how many characters appear an odd number of times. For the string to have a palindromic permutation, this sum must be less than 2 (allowing for the middle character in an odd-length palindrome). If this condition is satisfied, the method returns true; otherwise, it returns false.

Solution Approach

The solution uses a hash table to count the occurence of each character in the string. This is done using Python's Counter class from the collections module, which upon passing the string, it will return a dictionary where keys are characters from the string and values are the counts of those characters.

Counter(s).values()

Once we have the character counts, we need to determine how many characters have odd counts. In a palindromic string, at most one character can appear an odd number of times (which would be the middle character in an odd length palindrome).

We can find the number of characters with odd counts using the following line of code:

sum(v & 1 for v in Counter(s).values())

Here, v & 1 is a bitwise AND operation that returns 1 if v is odd and 0 if v is even. This is because odd numbers have a least significant bit of 1. Running this operation in a comprehension and summing the results, we get the total number of characters with odd counts.

The condition for the string to potentially be a palindrome (after a permutation) is for the sum of odd counts to be less than 2. This makes sense because if the string length is even, there should be no characters with odd counts, and if the string length is odd, there should be only one.

The final return statement in the code checks this condition:

return sum(v & 1 for v in Counter(s).values()) < 2

If the sum is less than 2, the function returns true, indicating that a palindromic permutation is possible. If not, it returns false.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach. Consider the string s = "civic".

First, we pass this string to the Counter class to count the occurrences of each character:

from collections import Counter
character_counts = Counter("civic").values() # character_counts will be { 'c': 2, 'i': 2, 'v': 1 }

Here are the counts we get:

'c' appears 2 times
'i' appears 2 times
'v' appears 1 time

Now, we need to check how many characters have odd counts. Since 'c' and 'i' both appear an even number of times and 'v' appears an odd number of times, we will have:

sum(v & 1 for v in Counter("civic").values()) # This will compute to 1

The bitwise AND operation (v & 1) will return 1 for the count of 'v' as it's odd and 0 for the counts of 'c' and 'i' since those are even. Adding these up gives us 1.

Since the sum of odd counts is 1, which is less than 2, the string s = "civic" has a palindromic permutation. The permutation "civic" itself is a palindrome.

Hence, according to the final check:

return sum(v & 1 for v in Counter(s).values()) < 2

The function will return true, indicating that it's indeed possible to permute the string s = "civic" into a palindrome.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def canPermutePalindrome(self, s: str) -> bool:
5        # Count the occurrences of each character in the string
6        char_count = Counter(s)
7      
8        # Calculate the number of characters that appear an odd number of times
9        odd_count = sum(value % 2 for value in char_count.values())
10      
11        # A string can be permuted into a palindrome if it has at most one character 
12        # with an odd occurrence count (which would be the middle character)
13        return odd_count < 2
14

1class Solution {
2    // This method checks if a permutation of the input string can form a palindrome
3    public boolean canPermutePalindrome(String s) {
4        // Frequency array to store the count of each character assuming only lowercase English letters
5        int[] charCount = new int[26];
6      
7        // Iterate over each character in the string
8        for (char character : s.toCharArray()) {
9            // Increment the count for this character
10            charCount[character - 'a']++;
11        }
12      
13        // Counter for the number of characters that appear an odd number of times
14        int oddCount = 0;
15      
16        // Iterate over the frequency array
17        for (int count : charCount) {
18            // If the count of a character is odd, increment the oddCount
19            if (count % 2 == 1) {
20                oddCount++;
21            }
22        }
23      
24        // A string can form a palindrome if there is no more than one character that appears an odd number of times
25        return oddCount < 2;
26    }
27}
28

1class Solution {
2public:
3    // Function to check if a permutation of the input string can form a palindrome
4    bool canPermutePalindrome(string s) {
5        // Create a vector to count occurrences of each lowercase letter
6        vector<int> charCounts(26, 0); // Initialize counts to 0 for 'a'-'z'
7
8        // Count occurrences of each character in the input string
9        for (char c : s) {
10            // Increase the count of the current character
11            ++charCounts[c - 'a']; // Assuming input string has only lowercase letters
12        }
13
14        // Variable to keep track of the number of characters with odd counts
15        int oddCount = 0;
16
17        // Iterate through the character counts
18        for (int count : charCounts) {
19            // If the count is odd, increment the odd count
20            oddCount += count % 2; // Count is odd if % 2 is 1
21        }
22
23        // A string can be permuted to form a palindrome if there is at most one character with an odd count
24        return oddCount < 2;
25    }
26};
27

1function canPermutePalindrome(s: string): boolean {
2    // Create an array to count occurrences of each lowercase letter.
3    const charCounts: number[] = new Array(26).fill(0);
4
5    // Iterate over each character in the string.
6    for (const char of s) {
7        // Increment the count for the current character.
8        ++charCounts[char.charCodeAt(0) - 'a'.charCodeAt(0)];
9    }
10
11    // Use filter to count how many characters have an odd number of occurrences.
12    const oddCounts = charCounts.filter(count => count % 2 === 1).length;
13
14    // For a string to be permutable to a palindrome, there must be 
15    // at most one character with an odd count (which would be the middle character).
16    return oddCounts < 2;
17}
18

Time and Space Complexity

The time complexity of the given code snippet is O(n), where n is the length of the input string s. This is because we're iterating through the string once to create a counter (a dictionary) of the characters, which takes O(n) time. Then, we iterate through the values in the counter, which in the worst case contains n unique characters, to calculate the sum of the odd counts. However, since the number of unique characters is typically far less than n, this is still considered O(n) complexity.

The space complexity of the given code snippet is also O(n) for the same reason. As we create a counter that could potentially have as many entries as there are characters in the string if all characters are unique. Hence, the space required for the counter can grow linearly with the size of the input string s.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function call

Determine return value

Determine how many recursive calls will be made

Tracing the recursive calls