Spoj Problem AIBOHP-Aibohphobia[Java Solutio] using Dynamic Programming

   Spoj Problem AIBOHP-Aibohphobia[Java Solution] using Dynamic Programming

Problem Statement:-http://www.spoj.com/problems/AIBOHP/

Hint:- Find length of LONGEST COMMON SUBSEQUENCE in orignal string and reverse of string and subtract it from length of orignal string.

Longest Common Subsequence Problem easily solved using Dynamic Programming.

Required Value=length of string - LCS(string,reverse of string)

A nice detailed tutorial to find Longest Common Sub-Sequence is

Java Program:-

 /**
 * @(#)AIBOHP.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2016/4/11
 */
import java.io.*;
import java.util.*;

class AIBOHP {

    public static void main(String args[])throws IOException{
   
   
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    long T=Long.parseLong(br.readLine());
   
    while(T--!=0){
    
    StringBuilder str=new StringBuilder(br.readLine());
    String ostr=str.toString();
    System.out.println(ostr.length()-LCS(ostr,str.reverse().toString()));
   
    }
   
    }
    
    public static int LCS(String x,String y){
   
    int dp[][]=new int[x.length()+1][y.length()+1];
   
    for(int i=0;i<=x.length();i++){
    for(int j=0;j<=y.length();j++){
    if(i==0||j==0){
    dp[i][j]=0;
    continue;
    }
   
    if(x.charAt(i-1)==y.charAt(j-1)){
    dp[i][j]=dp[i-1][j-1]+1;
    }else{
    dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
    }
   
    }
    }
    return dp[x.length()][y.length()];
    }
      
}

Input:-

1
fft

Output:-

1

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------