置換え文字列のパインドームを取得

Question

エレナには、英小文字のアルファベット（つまりa-z）の文字列Sがあります。彼女は、文字列内の任意の文字を他の文字と置き換えることができ、何度もこの置換を実行できます。彼女は、文字列pにサブ文字列linkedinが含まれるように、sからパリンドローム文字列pを作成したいとします。なお、エリナはSからパリンドローム列Pを作成できることが保証される S. サンプルテストケースからパリンドローム列Pを作成するために必要な操作の最小数である見つける：

最初のテストケース：S =

「linkedininininin」

説明：

  linkedin (i) (n) (i) (n) (i) ni (n) 

        (n) (i) (d) (e) (k) (l) 

      p = "linkedinnideknil" 

出力される6

第テストケース：S = "fulrokxeuolnzxltiiniabudyyozvulqbydmaldbxaddmkobhlplkaplgndnksqidkaenxdacqtsskdkdddls"

出力は、それがなってきたか、

46は、ここで私は第二のテストケースの出力を取得することができませんでしたある出力46

第3のテストケース：

   S="linkaeiouideknil" 

       P="linkedinnideknil" 
    Output = 4 

Answer 1

ここ

での時間計算量を持つコードに）。

import java.io.*; 
import java.util.*; 

class TestClass { 
    public static void main(String args[]) throws Exception { 
    Scanner sc = new Scanner(System.in); 
    String input = sc.next(); 
    String ln = "linkedin"; 
    String rln= "nideknil"; 
    int limit, limit2; 
    int len = input.length(); 

    if(len%2==0){ 
     limit=len/2-7; 
     limit2=len/2-1; 
    }else{ 
     limit=(len+1)/2-7; 
     limit2= (len-1)/2 -1; 
    } 
    int max=0,index=0; 
boolean rev=false; 
    for(int i = 0; i<=len-8;i++){ 
     int count1=0, count2=0; 

     if(i==limit){ 
      if(len%2==0){ 
       i=len/2; 

      }else{ 
       i=(len-1)/2; 
      } 

     } 

    String temp=input.substring(i,i+8); 

     for(int j=0;j<8;j++){ 
      if(ln.charAt(j)==temp.charAt(j)){ 
       count1++; 
      } 
      if(rln.charAt(j)==temp.charAt(j)){ 
       count2++; 
      } 
      int temp2 = count1 > count2 ? count1 : count2; 

      if(temp2>max){ 
       index=i; 
       max=temp2; 
       if(temp2==count2){ 
        rev=true; 
       } 
       else 
       rev=false; 
      } 

     } 
    } 

    int replace=0; 
    char in[]= input.toCharArray(); 
    int i,j; 

    for(i= index,j=0;i<index+8;j++,i++){ 
    if(rev){ 
     if(rln.charAt(j)!=in[i]){ 
      replace++; 

      in[i]=rln.charAt(j); 
     } 
    } else{ 
     if(ln.charAt(j)!=in[i]){ 
      replace++; 

      in[i]=ln.charAt(j); 
     } 
    } 
    } 

    for(j=0,i = len-1; j<=limit2 ;i--,j++){ 
     if(in[i]!=in[j]){ 
      replace++; 
     } 
    } 


     System.out.println(replace); 
    } 
}