Palindrome Permutation

easy hash map string

Problem

Given a string, return true if a permutation of it could form a palindrome.

Inputs = "carerac"

Outputtrue

counts: c=2, a=2, r=2, e=1 (one odd). Rearrange as "racecar".

def can_permute_palindrome(s):
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    odd = sum(1 for v in counts.values() if v % 2)
    return odd <= 1

function canPermutePalindrome(s) {
  const counts = {};
  for (const ch of s) counts[ch] = (counts[ch] || 0) + 1;
  let odd = 0;
  for (const v of Object.values(counts)) if (v % 2) odd++;
  return odd <= 1;
}

class Solution {
    public boolean canPermutePalindrome(String s) {
        int[] c = new int[128];
        for (char ch : s.toCharArray()) c[ch]++;
        int odd = 0;
        for (int v : c) if (v % 2 == 1) odd++;
        return odd <= 1;
    }
}

bool canPermutePalindrome(string s) {
    int c[128] = {0};
    for (char ch : s) c[ch]++;
    int odd = 0;
    for (int v : c) if (v % 2 == 1) odd++;
    return odd <= 1;
}

Explanation

A string can be rearranged into a palindrome only if its letters can mirror around the center. That gives one clean rule: at most one letter may have an odd count. Everything else must pair up.

So we count each character's frequency with a hash map (or a 128-slot array), then count how many of those frequencies are odd.

Why it works: in a palindrome, letters on the left mirror the right, so every letter needs an even count — except a single middle letter, which may sit alone with an odd count.

Example: s = "carerac". Counts are c=2, a=2, r=2, e=1. Only e is odd (just one odd), so the answer is true — it can form "racecar".

If two or more letters had odd counts, no single center could absorb them, so the function returns false.

Time: O(n) Space: O(σ)