LongestPalindromicSubstring.java

/*
    Given a string, find the longest palindromic substring.

    Maintains right upper half of the table.
 */
public class LongestPalindromicSubstring {
    // complexity: time O(n^2), space O(n^2)
    static int findLPS(String S) {
        int n = S.length();
        boolean[][] memo = new boolean[n][n];

        // length 1 substring is a palindrome
        // diagonal
        int max = 1;
        for (int i=0; i<n; i++) {
            memo[i][i] = true;
        }
        // check length 2 substring
        int start = 0;
        for (int i=0; i<n-1; i++) {
            if (S.charAt(i) == S.charAt(i+1)) {
                memo[i][i+1] = true;
                start = i;
                max = 2;
            }
        }
        // check length longer than 2
        for (int k = 3; k<=n; k++) {
            for (int i=0; i<n-k+1; i++) {
                // ending index
                int j = i + k -1;
                if (memo[i+1][j-1] && (S.charAt(i) == S.charAt(j))) {
                    memo[i][j] = true;
                    if (k > max) {
                        start = i;
                        max = k;
                    }
                }
            }
        }
        System.out.println("longest: " + S.substring(start, start+max));
        return max;
    }
    public static void main(String[] args) {
        String S = "forgeeksskeegfor";
        System.out.println(findLPS(S));
    }
}

/*
References:
http://www.geeksforgeeks.org/longest-palindrome-substring-set-1/
http://www.programcreek.com/2013/12/leetcode-solution-of-longest-palindromic-substring-java/
*/