题解 | 游游的字符重排

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        scanner.close();
        
        int n = s.length();
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        
        int[] count = new int[1]; // 使用数组传递计数（Java值传递限制）
        backtrack(new StringBuilder(), freq, n, count);
        
        System.out.println(count[0]);
    }
    
    private static void backtrack(StringBuilder sb, int[] freq, int n, int[] count) {
        if (sb.length() == n) {
            count[0]++;
            return;
        }
        
        for (int i = 0; i < 26; i++) {
            if (freq[i] > 0) {
                // 如果当前字符串非空，检查新字符是否与最后一个字符相等
                if (sb.length() > 0) {
                    char lastChar = sb.charAt(sb.length() - 1);
                    if (i == (lastChar - 'a')) {
                        continue; // 跳过相同字符，避免相邻相等
                    }
                }
                // 选择当前字符
                freq[i]--;
                sb.append((char) ('a' + i));
                backtrack(sb, freq, n, count);
                // 回溯
                sb.deleteCharAt(sb.length() - 1);
                freq[i]++;
            }
        }
    }
}

使用回溯法（DFS）生成所有可能的排列，并在生成过程中通过频率数组和相邻字符检查来避免无效序列，同时处理重复字符以确保计数正确