Tuesday 19 July 2016

Longest Palindromic Substring

    Brute force

Time complexity: O ( n^3 )
Auxiliary complexity: O ( 1 ).

    Dynamic programming

Time complexity: O ( n^2 )
Auxiliary complexity: O ( n^2)

package geeks.dp;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class LongestPalindromeSubstring {
       private static int max = 0;

       public static void main(String[] argsthrows IOException {
           BufferedReader buffReader = new BufferedReader(
                                         new InputStreamReader(System.in));
           System.out.println("Input String !!");
           char[] inputChars = buffReader.readLine().toCharArray();
             
           int length = inputChars.length;
             
           int[][] dp = new int[length+1][length+1];
             
           for (int i = 1; i <= lengthi++) {
               for (int j = 1; j <=lengthj++) {
                   if(inputChars[i-1]==inputChars[length-j]) {
                        dp[i][j] = dp[i-1][j-1]+1;
                   } else {
                        dp[i][j] = 0;
                   }
                   max = Math.max(dp[i][j], max );
               }
          }
          System.out.println(max);
       }
}

Output:
Input String !!
geeksskeeggeeksskeeg
20

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...