Last active
November 2, 2021 12:23
-
-
Save ali-alaei/b799d50536c8f7af3a1b8dae741c2c46 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Main | |
{ | |
private String findLongestPalindromicSubstring(String input) | |
{ | |
//If empty, does not analyze the string | |
if(input.isEmpty()) | |
{ | |
return ""; | |
} | |
//holds the length of the string | |
int strLen = input.length(); | |
int longestSoFar = 0, startIndex = 0, endIndex = 0; | |
//A 2D array for dynamic programming table | |
//the type is boolean because it can only hold the value of 0 or 1 | |
boolean[][] DPTable = new boolean[strLen][strLen]; | |
// Looping over the whole string | |
for(int j = 0; j < strLen; j++) | |
{ | |
//The main diagonal of the table is always true or 1. | |
DPTable[j][j] = true; | |
for(int i = 0; i < j; i++) | |
{ | |
//checks the two conditions discussed earlier for | |
//palindromic substrings | |
if(input.charAt(i) == input.charAt(j) && | |
(j-i<=2 || DPTable[i+1][j-1])) | |
{ | |
// If the conditions are met, then we set the cell to true | |
DPTable[i][j] = true; | |
//Compares the length of the current substring to the | |
//the longest substring. | |
if(j-i+1 > longestSoFar) | |
{ | |
//If the current substring length is longer, replace | |
//the corresponding variables with the new values | |
longestSoFar = j-i+1; | |
startIndex = i; | |
endIndex = j; | |
} | |
} | |
} | |
} | |
//Returns the longest palindromic substring | |
return input.substring(startIndex, endIndex+1); | |
} | |
public static void main(String[] args) | |
{ | |
//Testing the function | |
String input = "aabbab"; | |
Main test = new Main(); | |
System.out.println(test.findLongestPalindromicSubstring(input)); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment