Brute force
Time complexity: O ( n^3 )
Auxiliary complexity: O ( 1 ).
Auxiliary complexity: O ( 1 ).
Dynamic programming
Time complexity: O ( n^2 )
Auxiliary 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
No comments:
Post a Comment