📌 Palindrome Permutation

Read Time:1 Minute, 16 Second

A palindrome permutation checks whether a string’s characters can be rearranged to form a palindrome.

Palindrome Rules

A palindrome reads the same forward and backward
Characters must appear in pairs
At most one character is allowed to appear an odd number of times

String Length	Allowed Odd Count
Even	0
Odd	1

Steps to Check

Remove spaces
(Optional) Convert to lowercase
Count frequency of each character
Count characters with odd frequency
If oddCount ≤ 1 → ✅ Palindrome permutation possible

Example: `"tact coa"`

Step 1: Remove space

tactcoa

Character	Count
t	2
a	2
c	2
o	1

Step 3: Odd count = 1 (o)

Step 4:

oddCount ≤ 1 → TRUE

Palindrome permutation exists

Possible Palindrome

taco cat

Interview One-Liner

“A string can form a palindrome permutation if no more than one character has an odd frequency.”

Time & Space Complexity

Time: O(n)
Space: O(1) (fixed alphabet)

Go Program: Palindrome Permutation

package main

import (
	"fmt"
)

func isPalindromePermutation(s string) bool {
	freq := make(map[rune]int)

	// Count characters (ignore spaces)
	for _, ch := range s {
		if ch != ' ' {
			freq[ch]++
		}
	}

	oddCount := 0

	// Check odd frequencies
	for _, count := range freq {
		if count%2 != 0 {
			oddCount++
		}
	}

	return oddCount <= 1
}

func main() {
	str := "tact coa"

	if isPalindromePermutation(str) {
		fmt.Println("Palindrome permutation possible")
	} else {
		fmt.Println("Palindrome permutation NOT possible")
	}
}