正浩笔试编程第二题 2022.3.7

n长的小写字符串 求两两不相邻的组合

public class Main{
    public static void main(String[] args){

        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        String s = scan.next();
        int[] alpha = new int[26];

        boolean flag = true;
        for(int i=0;i<s.length();i++){
            alpha[s.charAt(i)-'a']++;
            if(alpha[s.charAt(i)-'a']>(n/2)) flag=false;
        }
        if(!flag){
            System.out.println("no");
            return;
        }
        System.out.println("yes");
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<26;i++){
            if(dfs(stack,alpha,i)){
                for(Integer j:stack){
                    System.out.print((char)(j+'a'));
                }
                System.out.println();
                break;
            }

        }
    }
    public static boolean dfs(Stack<Integer> s,int[] alpha,int a){
        if(alpha[a]==0) return false;
        if(!s.isEmpty()&&a==s.peek()) return false;
        s.add(a);
        alpha[a]--;
        boolean ans=true;
        boolean flag=false;
        for(int i=0;i<26;i++){
            if(alpha[i]!=0){
                flag=true;
                if(dfs(s,alpha,i)) return true;
            }
        }
        if(!flag){
            return  true;
        }
        s.pop();
        alpha[a]++;
        return false;
    }

}