Longest Palindromic Substring

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

Description

Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

Example 1:

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

Example 2:

Input: s = "cbbd"
Output: "bb"

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

Constraints:

• 1 <= s.length <= 1000

• s consist of only digits and English letters (lower-case and/or upper-case),

Solutions

Solution 1 Longest common Substring

common mistake

Some people will be tempted to come up with a quick solution, which is unfortunately flawed (however can be corrected easily):

Reverse SS and become S'S′. Find the longest common substring between SS and S'S′, which must also be the longest palindromic substring.

This seemed to work, let’s see some examples below.

For example, SS = "caba", S'S′ = "abac".

The longest common substring between SS and S'S′ is "aba", which is the answer.

Let’s try another example: SS = "abacdfgdcaba", S'S′ = "abacdgfdcaba".

The longest common substring between SS and S'S′ is "abacd". Clearly, this is not a valid palindrome.

We could see that the longest common substring method fails when there exists a reversed copy of a non-palindromic substring in some other part of SS. To rectify this, each time we find a longest common substring candidate, we check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate.

This gives us an O(n^2 ) Dynamic Programming solution which uses O(n^2 ) space (could be improved to use O(n) space).

Solution 2 Brute force

The obvious brute force solution is to pick all possible starting and ending positions for a substring, and verify if it is a palindrome.

Complexity Analysis

• Time complexity : O(n^3).

• Space complexity : O(1).

Solution 3 Dynamic Programming

Complexity Analysis

• Time complexity : O(n^2). This gives us a runtime complexity of O(n^2).

• Space complexity : O(n^2). It uses O(n^2) space to store the table.

Solution 4 Expand around center

class Solution {
public:
    string longestPalindrome(string s) {
     
        if(s.empty()) return "";
        
        // max length of palindrome
        int maxL = 0;
        
        // start index of max length palindrome
        int lindex = 0;
        
        // string length
        int l = s.length();
        
        // Expand from center for every index of the string  
        for(int i=0;i<l;i++)
        {
            // checking for odd length palindrom => "aba" => both left and right index is 1 when i =1
            int oddlen = expandFromCenter(s,i,i);
            
            // checking for even length palindrom => "abba" => left = 1, right = 2 when i =1
            int evenlen = expandFromCenter(s,i,i+1);

            // find max length between odd and even length palindrome
            int len = max(oddlen,evenlen);
            
            // if palindrome length is greater than maxL then update maxL
            if(maxL<len)
            {
                maxL = len;
                
                // If i is the center then start index will be:  i - (len-1)/2 as 2/2==1 and 3/2==1
                lindex = i - (len-1)/2;
            }
        }
        
        // return substring starting from lindex and length of maxL
        return s.substr(lindex,maxL);
    }
    
    // Expand from center and keep expanding  in to left and right
    // as long as left element and right element are equal
    int expandFromCenter(string &s, int left, int right)
    {        
        int l = s.length(); 
        
		// Expand in to left and right as long as left and right index element are equal or their is no mismatch
        while(left>=0 && right<l && s[left]==s[right])
        {
            left--;
            right++;
        }
        
        // final valid right index : R-1
        // final valid left index: L+1
        // So their inclusive length: (R-1) - (L+1) + 1 => R-L-2+1 => R-L-1 
        return right - left - 1;
    }
};

Complexity Analysis

• Time complexity : O(n^2). Since expanding a palindrome around its center could take O(n) time, the overall complexity is O(n^2).

• Space complexity : O(1).

Solution 5 Manacher's algorithm

There is even an O(n) algorithm called Manacher's algorithm, explained here in detail. However, it is a non-trivial algorithm, and no one expects you to come up with this algorithm in a 45 minutes coding session. But, please go ahead and understand it, I promise it will be a lot of fun.