Palindromic Permutation

Problem Link

Anagram Palindrome – GeeksforGeeks

Problem Statement

Given a string S, check if characters of the given string can be rearranged to form a palindrome.

Return 1 if it is possible to convert the given string into a palindrome, else return 0.

Examples

Example 1:

Input: S = "geeksogeeks"
Output: 1
Explanation: The string can be converted into a palindrome: geeksoskeeg

Example 2:

Input: S = "geeksforgeeks"
Output: 0
Explanation: The given string can't be converted into a palindrome.

Constraints

• 1 <= |S| <= 10⁵

• S consists of lowercase English letters.

Intuition

A string can be rearranged into a palindrome if:

• Even length: All characters must occur even number of times.

• Odd length: All characters must occur even number of times except one character, which can occur once (center character).

Hence, we can simply count the frequency of all characters, and count how many have odd frequencies.

Approach: Frequency Map + Odd Count Check

1. Create a frequency map (HashMap<Character, Integer>) to count occurrences of each character.

2. Traverse the map and count the number of characters that have odd frequencies.

3. If the number of odd frequency characters is > 1, then it’s not possible to rearrange the string into a palindrome.

4. Else, it is possible.

Java Code

class Solution {
    int isPossible(String S) {
        HashMap<Character, Integer> freq = new HashMap<>();

        for (char ch : S.toCharArray()) {
            freq.put(ch, freq.getOrDefault(ch, 0) + 1);
        }

        int oddCount = 0;

        for (int count : freq.values()) {
            if (count % 2 != 0) {
                oddCount++;
            }
        }

        return (oddCount <= 1) ? 1 : 0;
    }
}

Time and Space Complexity

Dry Run

Input:

S = "geeksogeeks"

Steps:

• Frequencies: g:2, e:4, k:2, s:2, o:1

• Characters with odd frequency: o

• Only one character with odd count → valid for palindrome

• Return: 1

Follow-Up: Optimized with Fixed-Size Array (Lowercase Only)

If input is only lowercase English letters, we can use an array of size 26 instead of HashMap:

int[] freq = new int[26];
for (char ch : S.toCharArray()) {
    freq[ch - 'a']++;
}
int oddCount = 0;
for (int count : freq) {
    if (count % 2 != 0) oddCount++;
}
return (oddCount <= 1) ? 1 : 0;

This reduces space to O(1) since array size is fixed.

Conclusion

This problem is a classic case of character frequency-based palindrome checking.

By counting how many characters have odd frequencies, we can determine if rearrangement into a palindrome is possible in linear time.