## Longest Palindromic Substring problem statement

Given a string s, find the longest palindromic substring in s.

Example:

``````Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: "cbbd"
Output: "bb"``````

## Longest Palindromic Substring solution in Java

Longest Palindromic Substring is a classic dynamic programming problem. To solve this, we maintain a 2D array `palindrom[i][j]` which is set to `true` if the substring `s(i,j)` is a palindrome, otherwise, it is set to `false`.

This array can be filled in a bottom-up manner:

``````For every i; palindrom[i][i] = true
For every (i, j); palindrom[i][j] = true if str[i] == str[j] && j-i <= 2
For every (i, j); palindrom[i][j] = true if str[i] == str[j] && palindrom[i+1][j-1]) == true``````

We also maintain a variable to keep track of the longest palindromic substring found so far (`longestSoFar`).

For every `(i,j)` such that `palindrom[i][j] = true`, we check if the length of the current palindrom (`j-i+1`) is greater than the longest palindrom found so far and set the longest palindrom accordingly.

Here is the complete solution:

``````import java.util.Scanner;

class LongestPalindromicSubstring {
private static String findLongestPalindromicSubstring(String input) {
if(input.isEmpty()) {
return "";
}
int n = input.length();
int longestSoFar = 0, startIndex = 0, endIndex = 0;
boolean[][] palindrom = new boolean[n][n];

for(int j = 0; j < n; j++) {
palindrom[j][j] = true;
for(int i = 0; i < j; i++) {
if(input.charAt(i) == input.charAt(j) && (j-i <= 2 || palindrom[i+1][j-1])) {
palindrom[i][j] = true;
if(j-i+1 > longestSoFar) {
longestSoFar = j-i+1;
startIndex = i;
endIndex = j;
}
}
}
}
return input.substring(startIndex, endIndex+1);
}
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
String input = keyboard.next();
System.out.println(findLongestPalindromicSubstring(input));
}
}``````
``````# Output
\$ javac LongestPalindromicSubstring.java
\$ java LongestPalindromicSubstring