字符串拼接

 给定M (0<M<=30)个字符(a-z)，从中取出任意字符(每个字符只能用一次)拼接成长度为N (0<N<=5)的字符串，要求相同的字符不能相邻，计算出给定的字符列表能拼接出多少种满足条件的字符串，输入非法或者无法拼接出满足条件的字符串则返回0。
 输入描述：给定的字符列表和结果字符串长度，中间使用空格(" ")拼接
 输出描述：满足条件的字符串个数

import java.util.*;

public class Main {
    static int res = 0;
    static boolean[] used;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int length = sc.nextInt();
        boolean check = false;
        
        // 检查输入字符是否合法（a-z）
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < 'a' || s.charAt(i) > 'z') {
                check = true;
                break;
            }
        }
        
        if (length > s.length() || check || length <= 0) {
            System.out.print("0");
        } else {
            used = new boolean[s.length()];
            char[] chars = s.toCharArray();
            Arrays.sort(chars); // 排序便于去重
            backtrack(chars, new StringBuilder(), length);
            System.out.print(res);
        }
    }
    
    public static void backtrack(char[] chars, StringBuilder path, int length) {
        // 终止条件：当前路径长度等于目标长度
        if (path.length() == length) {
            res++;
            return;
        }
        
        for (int i = 0; i < chars.length; i++) {
            // 跳过已使用的字符
            if (used[i]) {
                continue;
            }
            // 去重剪枝：跳过相同字符的前一个未使用字符
            if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) {
                continue;
            }
            // 相邻字符相同剪枝：检查当前字符是否与路径最后一个字符相同
            if (path.length() > 0 && path.charAt(path.length() - 1) == chars[i]) {
                continue;
            }
            // 做出选择
            used[i] = true;
            path.append(chars[i]);
            // 递归回溯
            backtrack(chars, path, length);
            // 撤销选择
            used[i] = false;
            path.deleteCharAt(path.length() - 1);
        }
    }
}