Can a String Be Rearranged into a Palindrome? Frequency Counting Approach

Direct Answer

Count each character's frequency, then check the parity: a string can be rearranged into a palindrome if and only if at most one character has an odd count. Even-length strings allow zero odd counts; odd-length allows exactly one (the middle char). O(n) time, O(k) space. You never build the palindrome - just count odds.

Deep Dive & Architecture

A palindrome reads the same from both ends, so almost every character must be placed in matching pairs. An even-length palindrome requires every frequency to be even. An odd-length palindrome may have exactly one odd frequency for its center.

Worked example: carrace

The counts are c=2, a=2, r=2, and e=1. Only e is odd, so the letters can be rearranged as racecar. In contrast, abc has three odd counts and cannot form a palindrome.

Count characters in a map or fixed alphabet array, then count how many frequencies are odd. The answer is true when that number is at most one. It is not necessary to generate the actual permutation.

The scan is O(n), followed by O(k) work over the distinct characters, which is O(n) overall. Storage is O(k). A set can also track odd characters by adding on an odd occurrence and removing on an even occurrence; the final set size gives the same test.

Normalization belongs to the contract. A phrase such as Tact Coa forms taco cat only if spaces are removed and letters are lowercased. Do not apply those rules unless the question asks for them.

Code Example

boolean canFormPalindrome(String s) {
    Set<Character> odd = new HashSet<>();
    for (char c : s.toCharArray()) {
        if (!odd.add(c)) odd.remove(c);   // toggle: in on odd, out on even
    }
    return odd.size() <= 1;               // at most one odd count
}

// s = "aabbc": a even, b even, c odd -> odd={c}, size 1 -> true (e.g. abcba)
// s = "aabbcd": c, d odd -> odd={c,d}, size 2 -> false

The toggle leaves exactly the odd-count characters in the set.

Common Mistakes & Pitfalls

• Generating permutations: exponential and wholly unnecessary.
• Requiring zero odds always: odd-length strings allow exactly one odd char.
• Building the palindrome: the question only asks if it can be formed.
• Case/space sensitivity: clarify whether to normalize before counting.