Palindrome Permutation

Problem Statement

Determining if a permutation of a given string s can form a palindrome is the essence of this problem. Consider what a palindrome is: a word, phrase, or sequence that reads the same forward and backward. If it is possible to rearrange the characters in the string s such that this condition is satisfied, the function should return true. If not, the function should return false. For instance, for the string "code", no permutation can form a palindrome, but for "aab" or "carerac", rearranging the characters can indeed result in a palindrome.

Examples

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.

Approach and Intuition

To understand whether a permutation of the string can form a palindrome, observe these key points based on the examples and constraints:

1. A palindrome reads the same forward and backward, implying symmetry. This symmetry generally translates to an even number of each character in the string, allowing pairs to be mirrored about a central point.

2. An exception to the even count rule is in odd-length palindromes, where one character can appear an odd number of times (acting as the central pivot), while all other characters must still have even counts.

3. From these observations, the steps to determine if a string can form a palindrome are as follows:

   1. Count the frequency of each character in the string.

   2. Check the number of characters that have an odd count.

      • If more than one character has an odd frequency count, it's impossible to rearrange the string into a palindrome.

      • If zero or one character has an odd frequency, then a palindrome permutation is possible.

Summing these insights, the solution involves counting character frequencies and then evaluating the frequency distribution to decide the possibility of forming a palindrome. With constraints allowing string lengths up to 5000 characters, the approach effectively handles large inputs efficiently by focusing on character counts and their properties rather than attempting to generate permutations.

Solutions

public class Solution {
    public boolean canFormPalindrome(String str) {
        Set<Character> charSet = new HashSet<>();
        for (int index = 0; index < str.length(); index++) {
            char c = str.charAt(index);
            if (!charSet.add(c))
                charSet.remove(c);
        }
        return charSet.size() <= 1;
    }
}