LeetCode (Algorithms#5) ‒ Longest Palindromic Substring

Problem

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Examples:

Given "cababade", return "ababa"
Given "gcaack", return "caac"

Solution

This problem is similar to that of the Longest Common Subsequence, and as most should suspect, can be solved using dynamic programming. Because we must consider all possible substrings as a palindrome, we can expect an (n)(n+1)/2=O(n^2) solution. There are quite a few ways to solve this in O(n^2), but the basic idea is that we keep track of all palindromes starting at i, and ending at j. When i==j and the characters at position i and j are equal, the character is a palindrome with itself of length 1. If the characters are equal and i!=j, then either the two same characters are next to each other, or are the beginning and end of a previous palindrome. In both cases we add 2 to account for the length of the character on both ends.

Below is the code for this approach. The loops run from the end of the string to produce a matrix A with the upper triangle containing lengths of palindromes. The maximum palindrome is kept track of and returned.

Time complexity: O(n^2)
Space complexity: O(n^2)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

public String longestPalindrome(String s) { int maxi = -1, maxj = -1, maxPal = 0, len = s.length(); int[][] A = new int[len][len]; for (int i = len - 1; i >= 0; i--) { for (int j = i; j < len; j++) { if (s.charAt(i) == s.charAt(j)) { if (i == j) A[i][j] = 1; else if (i+1 > j-1 || A[i+1][j-1] > 0) A[i][j] = A[i+1][j-1] + 2; if (A[i][j] > maxPal) { maxPal = A[i][j]; maxi = i; maxj = j; } } else { A[i][j] = 0; } } } return s.substring(maxi,maxj+1); }