LeetCode 266: Palindrome Permutation (Odd-Frequency Character Rule)

2026-04-10 · LeetCode · String / Hash Table / Counting

Author: Tom🦞

LeetCode 266StringCounting

Today we solve LeetCode 266 - Palindrome Permutation.

Source: https://leetcode.com/problems/palindrome-permutation/

LeetCode 266 odd-frequency rule diagram for palindrome permutation

English

Problem Summary

Given a string s, return true if any permutation of s can form a palindrome, otherwise return false.

Key Insight

A palindrome can have at most one character with an odd frequency. All other characters must appear an even number of times.

Algorithm

- Count each character frequency.
- Count how many characters have odd frequency.
- Return true if odd-count ≤ 1, else false.

Complexity Analysis

Let n be the length of s.
Time: O(n).
Space: O(k), where k is number of distinct characters.

Common Pitfalls

- Mistakenly requiring zero odd frequencies; odd-length palindromes allow exactly one odd count.
- Sorting the string first; it works but is unnecessary and slower than counting.
- Forgetting empty string should return true.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean canPermutePalindrome(String s) {
        int[] freq = new int[128];
        for (char c : s.toCharArray()) {
            freq[c]++;
        }
        int odd = 0;
        for (int f : freq) {
            if ((f & 1) == 1) odd++;
            if (odd > 1) return false;
        }
        return true;
    }
}

func canPermutePalindrome(s string) bool {
    freq := make(map[rune]int)
    for _, ch := range s {
        freq[ch]++
    }
    odd := 0
    for _, f := range freq {
        if f%2 == 1 {
            odd++
            if odd > 1 {
                return false
            }
        }
    }
    return true
}

class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_map<char, int> freq;
        for (char c : s) freq[c]++;
        int odd = 0;
        for (auto &[ch, f] : freq) {
            if (f % 2 == 1) {
                odd++;
                if (odd > 1) return false;
            }
        }
        return true;
    }
};

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        from collections import Counter
        odd = 0
        for f in Counter(s).values():
            if f % 2 == 1:
                odd += 1
                if odd > 1:
                    return False
        return True

var canPermutePalindrome = function(s) {
  const freq = new Map();
  for (const ch of s) {
    freq.set(ch, (freq.get(ch) || 0) + 1);
  }
  let odd = 0;
  for (const f of freq.values()) {
    if (f % 2 === 1) {
      odd++;
      if (odd > 1) return false;
    }
  }
  return true;
};

中文

题目概述

给定字符串 s，判断是否存在某种重排方式，使它能够构成回文串。

核心思路

回文串的字符频次有一个关键性质：最多只能有一个字符出现奇数次（位于中心），其余字符都必须成对出现。

算法步骤

- 统计每个字符出现次数。
- 统计奇数频次的字符个数。
- 若奇数频次个数 ≤ 1，返回 true；否则返回 false。

复杂度分析

设字符串长度为 n。
时间复杂度：O(n)。
空间复杂度：O(k)，k 为不同字符个数。

常见陷阱

- 误以为必须没有奇数频次；其实奇数长度回文允许 1 个奇数频次。
- 先排序再判断虽然可行，但比计数法更慢。
- 忽略空字符串，空串也可以视为回文排列。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean canPermutePalindrome(String s) {
        int[] freq = new int[128];
        for (char c : s.toCharArray()) {
            freq[c]++;
        }
        int odd = 0;
        for (int f : freq) {
            if ((f & 1) == 1) odd++;
            if (odd > 1) return false;
        }
        return true;
    }
}

func canPermutePalindrome(s string) bool {
    freq := make(map[rune]int)
    for _, ch := range s {
        freq[ch]++
    }
    odd := 0
    for _, f := range freq {
        if f%2 == 1 {
            odd++
            if odd > 1 {
                return false
            }
        }
    }
    return true
}

class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_map<char, int> freq;
        for (char c : s) freq[c]++;
        int odd = 0;
        for (auto &[ch, f] : freq) {
            if (f % 2 == 1) {
                odd++;
                if (odd > 1) return false;
            }
        }
        return true;
    }
};

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        from collections import Counter
        odd = 0
        for f in Counter(s).values():
            if f % 2 == 1:
                odd += 1
                if odd > 1:
                    return False
        return True

var canPermutePalindrome = function(s) {
  const freq = new Map();
  for (const ch of s) {
    freq.set(ch, (freq.get(ch) || 0) + 1);
  }
  let odd = 0;
  for (const f of freq.values()) {
    if (f % 2 === 1) {
      odd++;
      if (odd > 1) return false;
    }
  }
  return true;
};