LeetCode 266: Palindrome Permutation

Explanation

To determine if a given string can be rearranged into a palindrome, we can count the frequency of each character in the string. For a string to be a palindrome, there can be at most one character with an odd frequency (the middle character). All other characters should have an even frequency.

We will iterate over the characters in the string, maintaining a count of the frequencies of each character. If we encounter a character whose frequency is already odd, we decrement its count, making it even. If we encounter a character with an even frequency, we increment its count, making it odd. Finally, we check if there is at most one character with an odd frequency.

public boolean canPermutePalindrome(String s) {
    int[] charFreq = new int[128];
    int oddCount = 0;
    
    for (char c : s.toCharArray()) {
        charFreq[c]++;
        if (charFreq[c] % 2 == 0) {
            oddCount--;
        } else {
            oddCount++;
        }
    }
    
    return oddCount <= 1;
}