Code Logo

Anagram Palindrome

Published at25 Jul 2026
Created by
Easy 0 views
Like0

Given a string s, determine whether any anagram of s can form a palindrome. A palindrome reads the same forwards and backwards. An anagram is a rearrangement of characters.

The key insight: a palindrome can have at most one character with an odd frequency. All other characters must appear an even number of times. This is because in a palindrome, characters are paired symmetrically from both ends, and only the middle character (if the length is odd) can be unpaired.

Count the frequency of each character in the string. Then count how many characters have an odd frequency. If this count is 0 or 1, return true; otherwise return false. For an even-length string, all frequencies must be even. For an odd-length string, exactly one character can have an odd frequency.

This solution runs in O(n) time where n is the length of the string, using O(k) space where k is the character set size (constant for ASCII). The algorithm uses a frequency array or a hash map to count character occurrences efficiently.

Edge cases include empty strings (return true), single-character strings (always palindrome), strings with special characters or spaces, and Unicode strings where character representation might differ.

Example Input & Output

Example 1
Input
"abc"
Output
false
Explanation

Two chars with odd count (a,b,c all odd)

Example 2
Input
"aab"
Output
true
Explanation

Can be rearranged to aba (palindrome)

Example 3
Input
"carrace"
Output
true
Explanation

Can be rearranged to racecar

Example 4
Input
"racecar"
Output
true
Explanation

racecar itself is a palindrome

Example 5
Input
"ab"
Output
false
Explanation

Two chars both odd, palindrome impossible

Algorithm Flow

Recommendation Algorithm Flow for Anagram Palindrome
Recommendation Algorithm Flow for Anagram Palindrome

Solution Approach

Determine if any permutation of a string can form a palindrome. A string can form a palindrome if at most one character has an odd frequency. Count character frequencies. If more than one character has an odd count, return false; otherwise return true.

function canPermutePalindrome(s) {
  var freq = {};
  for (var i = 0; i < s.length; i++) freq[s[i]] = (freq[s[i]] || 0) + 1;
  var odd = 0;
  for (var key in freq) {
    if (freq[key] % 2 !== 0) odd++;
  }
  return odd <= 1;
}

A palindrome can have at most one character with an odd count (the middle character in odd-length strings). All other characters must appear in even numbers.

Time complexity is O(n), space complexity is O(k).

Best Answers

java
class Solution {
    public boolean solution(String s) {
        int[] freq = new int[128];
        for (int i = 0; i < s.length(); i++) freq[s.charAt(i)]++;
        int odd = 0;
        for (int v : freq) if (v % 2 != 0) odd++;
        return odd <= 1;
    }
}