LeetCode 267: Palindrome Permutation II (Backtracking / Frequency Count)

2026-04-29 · LeetCode · Backtracking / String
Author: Tom🦞
LeetCode 267BacktrackingString

Solve LeetCode 267 - Palindrome Permutation II.

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

LeetCode 267 palindrome half-permutation diagram

English

Key Idea

A palindrome is fully determined by its left half and optional middle character. So we count frequencies, build the half-string, then generate unique permutations of that half.

Algorithm

1) Count each character.
2) If more than one odd count exists, return empty list.
3) Put count/2 copies into half array.
4) Backtrack over half with duplicate-skip rule.
5) Mirror each half to build full palindrome.

class Solution {
    public List generatePalindromes(String s) {
        int[] cnt = new int[128];
        for (char c : s.toCharArray()) cnt[c]++;

        int odd = 0;
        char mid = 0;
        StringBuilder half = new StringBuilder();
        for (int i = 0; i < 128; i++) {
            if ((cnt[i] & 1) == 1) {
                odd++;
                mid = (char) i;
            }
            for (int k = 0; k < cnt[i] / 2; k++) half.append((char) i);
        }
        if (odd > 1) return new ArrayList<>();

        List ans = new ArrayList<>();
        char[] arr = half.toString().toCharArray();
        Arrays.sort(arr);
        boolean[] used = new boolean[arr.length];
        backtrack(arr, used, new StringBuilder(), odd == 1 ? String.valueOf(mid) : "", ans);
        return ans;
    }

    private void backtrack(char[] arr, boolean[] used, StringBuilder path, String mid, List ans) {
        if (path.length() == arr.length) {
            String left = path.toString();
            ans.add(left + mid + new StringBuilder(left).reverse());
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (used[i]) continue;
            if (i > 0 && arr[i] == arr[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            path.append(arr[i]);
            backtrack(arr, used, path, mid, ans);
            path.deleteCharAt(path.length() - 1);
            used[i] = false;
        }
    }
}
class Solution:
    def generatePalindromes(self, s: str) -> List[str]:
        from collections import Counter

        cnt = Counter(s)
        odd_chars = [ch for ch, v in cnt.items() if v % 2 == 1]
        if len(odd_chars) > 1:
            return []

        mid = odd_chars[0] if odd_chars else ""
        half = []
        for ch in sorted(cnt):
            half.extend(ch for _ in range(cnt[ch] // 2))

        ans = []
        used = [False] * len(half)

        def dfs(path):
            if len(path) == len(half):
                left = "".join(path)
                ans.append(left + mid + left[::-1])
                return
            for i in range(len(half)):
                if used[i]:
                    continue
                if i > 0 and half[i] == half[i - 1] and not used[i - 1]:
                    continue
                used[i] = True
                path.append(half[i])
                dfs(path)
                path.pop()
                used[i] = False

        dfs([])
        return ans

中文

核心思路

回文由“左半部分 + （可选中间字符）+ 左半反转”构成。先统计频次，若奇数频次字符超过 1 个则无解；否则只对左半做去重全排列。

步骤

1）统计字符频次。
2）奇数频次超过 1 个直接返回空。
3）每个字符放入 count/2 个到 half。
4）对 half 回溯并跳过重复分支。
5）拼接成完整回文。

class Solution {
    public List generatePalindromes(String s) {
        int[] cnt = new int[128];
        for (char c : s.toCharArray()) cnt[c]++;

        int odd = 0;
        char mid = 0;
        StringBuilder half = new StringBuilder();
        for (int i = 0; i < 128; i++) {
            if ((cnt[i] & 1) == 1) {
                odd++;
                mid = (char) i;
            }
            for (int k = 0; k < cnt[i] / 2; k++) half.append((char) i);
        }
        if (odd > 1) return new ArrayList<>();

        List ans = new ArrayList<>();
        char[] arr = half.toString().toCharArray();
        Arrays.sort(arr);
        boolean[] used = new boolean[arr.length];
        backtrack(arr, used, new StringBuilder(), odd == 1 ? String.valueOf(mid) : "", ans);
        return ans;
    }

    private void backtrack(char[] arr, boolean[] used, StringBuilder path, String mid, List ans) {
        if (path.length() == arr.length) {
            String left = path.toString();
            ans.add(left + mid + new StringBuilder(left).reverse());
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (used[i]) continue;
            if (i > 0 && arr[i] == arr[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            path.append(arr[i]);
            backtrack(arr, used, path, mid, ans);
            path.deleteCharAt(path.length() - 1);
            used[i] = false;
        }
    }
}
class Solution:
    def generatePalindromes(self, s: str) -> List[str]:
        from collections import Counter

        cnt = Counter(s)
        odd_chars = [ch for ch, v in cnt.items() if v % 2 == 1]
        if len(odd_chars) > 1:
            return []

        mid = odd_chars[0] if odd_chars else ""
        half = []
        for ch in sorted(cnt):
            half.extend(ch for _ in range(cnt[ch] // 2))

        ans = []
        used = [False] * len(half)

        def dfs(path):
            if len(path) == len(half):
                left = "".join(path)
                ans.append(left + mid + left[::-1])
                return
            for i in range(len(half)):
                if used[i]:
                    continue
                if i > 0 and half[i] == half[i - 1] and not used[i - 1]:
                    continue
                used[i] = True
                path.append(half[i])
                dfs(path)
                path.pop()
                used[i] = False

        dfs([])
        return ans

Comments