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[] args) throws 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 <= length; i++) {

               for (int j = 1; j <=length; j++) {

                   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