Description

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

Analysis

The brute force method whose time is \(O(n^3)\) is obvious. But we want to explore the efficient method.

The first idea is to use dynamic programming. For the substring from index i to index j, there is a optimal substructure. If \(d[i][j]\) reflects whether the substring from \(i\) to \(j\) is a palindromic substring and \(s[i]\) is the \(i\)th character in the string, then

$$d[i][j]=(s[i]==s[j])\&\&((j-i<=2)||d[i+1][j-1])$$

It is easy to understand. In the loop we can set \(j\) from \(1\) to \(n\) and set \(i\) from \(i\) to \(j\). The time complexity and space complexity are both \(O(n^2)\).

The second idea can save many space than the first one. Choose each index as the center, and expand the string from the center to both sides if it will be a valid palindromic substring. Record the longest one and return it. The time complexity is also \(O(n^2)\). But the space complexity is \(O(1)\).

Solution

//Expand Around Center 
class Solution {
    String res="";
    public String longestPalindrome(String s) {
        if(s==null||s.length()==0) return "";
        for(int i=0;i<s.length();i++) { helper(s,i,i); helper(s,i,i+1); } return res; } public void helper(String s,int left,int right) { while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)) { if(right-left+1>res.length()) res=s.substring(left,right+1);
            left--;
            right++;
        }
        
    }
}

//dp
class Solution {
    public String longestPalindrome(String s) {
        if(s==null||s.length()==0) return "";
        String res="";
        boolean[][] d=new boolean[s.length()][s.length()];
        for(int j=0;j<s.length();j++)
        {
            for(int i=0;i<=j;i++)
            {
                d[i][j]=(s.charAt(i)==s.charAt(j))&&(j-i<=2||d[i+1][j-1]); if(d[i][j]==true&&j-i+1>res.length())
                {
                    res=s.substring(i,j+1);
                }
            }
        }
        return res;
    }
}

// Brute Force
class Solution {
    public String longestPalindrome(String s) {
        int maxlength=0;
        String maxpa="";
        int pa;
        for(int i=0;i<s.length();i++)
        {
            for(int j=i;j<s.length();j++)
            {
                pa=1;
                for(int k=i;k<=(i+j)/2;k++) { if(s.charAt(k)!=s.charAt(j-k+i)) { pa=0; break; } } if(pa==1) { if(j-i+1>maxlength)
                    {
                        maxlength=j-i+1;
                        maxpa=s.substring(i,j+1);
                    }
                }
            }
        }
        return maxpa;
    }
}

Reference

[1] https://github.com/EdwardShi92/Leetcode-Solution-Code/blob/master/LongestPalindromicSubstring.java

Leave a Reply

Your email address will not be published. Required fields are marked *