Leetcode: 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.

Solution:

Dynamic Programming O($n^2$) complexity and running time

If we want to know if the substring from i to j is a palindrome, we need that s[i]==s[j] and that the string from i+1 to j-1 is palindrome. We can apply this idea keeping a boolean matrix that the element (i,j) indicates whether the string from i to j is palindrome.
public class Solution {
    public String longestPalindrome(String s) {
        boolean[][] valid = new boolean[s.length()][s.length()];
        int max=1;
        int indmax=0;
        for (int i=0; i<s.length(); i++)
        {
            for(int j=0; j<s.length()-i; j++)
            {
                if(i==0)
                    valid[j][j]=true;
                else if(i==1)
                    valid[j][j+i]=s.charAt(j)==s.charAt(j+1);
                else
                    valid[j][j+i]= valid[j+1][j+i-1] && s.charAt(j)==s.charAt(j+i);
                if(valid[j][j+i] && max<i+1)
                {
                    max=i+1;
                    indmax=j;
                }
            }
        }
        return s.substring(indmax, indmax+max);
    }
}

Finding from the center O($n^2$) complexity and linear space

There exists 2n-1 possible centers for a palindrome, all the letters (odd length palindromes) plus all the spaces between them (even length palindromes). We can find the maximum palindrome of each center in O(n).

public class Solution {

    public String longestPalindrome(String s) {

        String sol =s.substring(0,1);

        //Odd palindromes

        for(int i=0; i<s.length(); i++)

        {

            String temp = longestPalindrome(s, i, true);

            if(temp.length()>sol.length())

                sol = temp;

        }

        for(int i=1; i<s.length(); i++)

        {

            String temp = longestPalindrome(s, i, false);

            if(temp.length()>sol.length())

                sol = temp;

        }

        return sol;

    }

    

    private String longestPalindrome(String s, int center, boolean centerInLetter)

    {

        int begin, end;

        if(centerInLetter)

        {

            begin = center; 

            end = center;

        }

        else

        {

            begin = center;

            end = center-1;

        }

        while(begin>0 && end<s.length()-1 && s.charAt(begin-1)==s.charAt(end+1))

        {

            begin--; end++;

        }

        return s.substring(begin, end+1);

    }

}

It exists a linear solution, Manacher's algorithm[1], that we will implement in a future post.

[1] Manacher, G. (1975). A New Linear-Time ``On-Line'' Algorithm for Finding the Smallest Initial Palindrome of a String. Journal of the ACM (JACM), 22(3), 346-351.