LeetCode Solution - Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/

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.

Given the string = "abcdzdcab", return "cdzdc".

Solution Reference: http://articles.leetcode.com/longest-palindromic-substring-part-i

Solution 1: Brute Force

// Time Complexity O(N^3)
public class Solution {
    /**    * @param s input string    * @return the longest palindromic substring    */
    * @param s input string
    * @return the longest palindromic substring
    */
    public String longestPalindrome(String s) {
        // Write your code here
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = 0; j + i < s.length(); j++) {
                if (isPalindrome(s, j, j + i)) {
                    return s.substring(j, j + i + 1);
                }
            }
        }
        return null;
    }
    private boolean isPalindrome(String s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

Solution 2: Dynamic Programming

Define P[ i, j ] ← true iff the substring Si … Sj is a palindrome, otherwise false.

Therefore,

P[ i, j ] ← ( P[ i+1, j-1 ] and Si = Sj )

The base cases are:

P[ i, i ] ← true
P[ i, i+1 ] ← ( Si = Si+1 )

// Time Complexity O(N^2), Space Complexity O(N^2)
public class Solution {
    /**     * @param s input string     * @return the longest palindromic substring     */
     * @param s input string
     * @return the longest palindromic substring
     */
    public String longestPalindrome(String s) {
        // Write your code here
        boolean[][] isPalindrome = new boolean[s.length()][s.length()];
        isPalindrome[s.length() - 1][s.length() - 1] = true;
        int start = 0, maxLength = 1;
        for (int i = 0; i < s.length() - 1; i++) {
            isPalindrome[i][i] = true;
            if (s.charAt(i) == s.charAt(i + 1)) {
                isPalindrome[i][i + 1] = true;
                start = i;
                maxLength = 2;
            }
        }
        for (int pos = 2; pos < s.length(); pos++) {
            for (int i = 0; i < s.length() - pos; i++) {
                int j = i + pos;
                if (isPalindrome[i + 1][j - 1] && s.charAt(i) == s.charAt(j)) {
                    isPalindrome[i][j] = true;
                    start = i;
                    maxLength = pos + 1;
                }
            }
        }        
        return s.substring(start, start + maxLength);
    }
}

Solution 3

// Time Complexity: O(N^2), Space Complexity O(1)
public class Solution {
    /**     * @param s input string     * @return the longest palindromic substring     */
     * @param s input string
     * @return the longest palindromic substring
     */
    public String longestPalindrome(String s) {
        // Write your code here
        String result = "";
        if (s == null) {
            return result;
        }
        String result1 = "";
        String result2 = "";
        int maxLength = 0;
        for (int i = 0; i < s.length(); i++) {
            result1 = expandPalindrome(s, i, i);
            if (result1.length() > maxLength) {
                maxLength = result1.length();
                result = result1;
            }
            result2 = expandPalindrome(s, i, i + 1);
            if ( result2.length() > maxLength ){
                maxLength = result2.length();
                result = result2;
            }
        }
        return result;
    }
    private String expandPalindrome(String s, int start, int end) {
        while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
            start--;
            end++;
        }
        return s.substring(start + 1, end);
    }
}