文字列の文字によって形成された回文の数を数える方法は？

Question

入力仕様

プログラムは テストする文字列を示す文字列Sです。英数字入力のすべての文字は入力から作成することができるユニークな回文数の合計をプリントアウトし、（500≤1≤LENGTH（S））の入力に基づいて

出力仕様

を小文字にします。 は具体的に、我々は、入力文字列「bbaa」を持っているし、我々は回文「BAAB」、「アバ」ので、入力文字列「bbaa」により作成された回文数の合計を持っていると仮定すると、2次さは、しかし、私が書いたコードです時間制限を超え、アルゴリズムが効率的ではありません。誰かが効率を改善できるようにアルゴリズムを構築する方法がありますか？回文を数えるはるかに簡単な方法はあり

import java.util.*; 
import java.lang.*; 
public class Problem 
{ 
     private static int count=0; 
    public static void main(String[] args) 
{ 

    Scanner stdin = new Scanner(System.in); 
    //int count=0; 
    while(stdin.hasNextLine()) 
    { String line=stdin.nextLine(); 
     char[] line_char=line.toCharArray(); 

     Arrays.sort(line_char); 
     StringBuilder strbuild=new StringBuilder(""); 
     solve(line_char,new boolean[line_char.length],strbuild); 
     //System.out.println(stdin.nextLine()); 
    } 
    System.out.println(count); 
    stdin.close(); 
} 

    public static void solve(char[] chararray,boolean[] used,StringBuilder strbuild){ 
    if(strbuild.length()==chararray.length){ 
     //System.out.println(strbuild.toString()); 
     if(checkpalindrome(strbuild)){ 
      count++; 
     } 
    }else{ 
     char rec=(char)(chararray[chararray.length-1]+1); 
     for(int i=0;i<chararray.length;i++){ 
      if(!used[i]&&rec!=chararray[i]){ 
       rec=chararray[i]; 
       strbuild.append(chararray[i]); 
       used[i]=true; 
       solve(chararray,used,strbuild); 
       strbuild.deleteCharAt(strbuild.length()-1); 
       used[i]=false; 
      } 
     } 
    } 

} 
public static boolean checkpalindrome(StringBuilder strbuild){ 
    String str=strbuild.toString(); 
    StringBuilder str1=new StringBuilder(strbuild); 
    return str.equals(str1.reverse().toString()); 
} 

}

Answer 1

：ここ

が、私はこの質問のために書いたものです。私はコードを書くつもりはありませんが、そのアプローチについて説明します。

あなたが入力のすべての文字を使用する必要があるので、あなたは奇数回発生する最大1つの文字を持つことができます。だから最初にその状態を確認する必要があります。奇数の文字が複数ある場合、答えはゼロでなければなりません。さもなければ、奇数の文字（もしあれば）を取り出し、それを出力文字列の真ん中で想像してください。残りの文字はすべて偶数回発生します。しかし、現在、回文を生成することは、各文字数の半分を取って、それらの文字のすべての固有の順列を生成することと同じです。次に、順列、中間の文字（該当する場合）、および順列の逆で形成された各順列に対して回文が存在する。

だから、すべてあなたがしなければならない（存在する場合、単一の奇妙な文字を扱う後）半分の文字のすべてのユニークな順列をカウントしています。それはあなたの現在のアプローチよりも効率的に行う方が簡単なはずです。