Dynamic Programming

Longest Palindromic Substring

Rajeev SinghAlgorithms1 mins read

Longest Palindromic Substring

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
bababbdbababad
babab