回文排列 II

/*
 * 思路：
 * 1. 与传统方法类似，我们需要生成字符串的回文排列。
 * 2. 使用Java Stream处理字符计数，并生成半个回文的排列。
 * 3. 拼接排列的反转部分和中间字符，生成完整的回文排列。
 */
 
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
 
public class PalindromePermutationIIStream {
    public List<String> generatePalindromes(String s) {
        Map<Character, Long> charCount = s.chars().mapToObj(c -> (char) c)
                .collect(Collectors.groupingBy(c -> c, Collectors.counting()));
        String mid = charCount.entrySet().stream()
                .filter(entry -> entry.getValue() % 2 != 0)
                .map(entry -> String.valueOf(entry.getKey()))
                .reduce((a, b) -> "").orElse("");
        if (mid.length() > 1) return new ArrayList<>(); // 超过一个奇数字符
        List<Character> half = charCount.entrySet().stream()
                .flatMap(entry -> IntStream.range(0, (int) (entry.getValue() / 2)).mapToObj(i -> entry.getKey()))
                .collect(Collectors.toList());
        List<String> halfPermutations = new ArrayList<>();
        backtrack(halfPermutations, half, new boolean[half.size()], new StringBuilder());
        return halfPermutations.stream()
                .map(halfStr -> halfStr + mid + new StringBuilder(halfStr).reverse().toString())
                .collect(Collectors.toList());
    }
 
    private void backtrack(List<String> result, List<Character> half, boolean[] used, StringBuilder sb) {
        if (sb.length() == half.size()) {
            result.add(sb.toString());
            return;
        }
        IntStream.range(0, half.size()).forEach(i -> {
            if (!used[i] && (i == 0 || half.get(i) != half.get(i - 1) || used[i - 1])) {
                used[i] = true;
                sb.append(half.get(i));
                backtrack(result, half, used, sb);
                sb.deleteCharAt(sb.length() - 1);
                used[i] = false;
            }
        });
    }
}