One of the solution for finding the longest palindromic substring could not be understood

Question

Refer to this article on leetcode, there's a common mistake for solving the longest palindromic substring problem:

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

For instance:

S = “abacdfgdcaba”, S’ = “abacdgfdcaba”.

The longest common substring between S and S’ is “abacd”. Clearly, this is not a valid palindrome.

But the following rectification I could not understand well. Could anyone explain it with an step-by-step procedure/example? Thanks!

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.

Answer 1

There are efficient algorithms for computing the longest palindromic substring by reversing the original substring. For example, the following:

1) create a generalized string S1#S2$ which takes O(n)
1) construct a suffix array O(n) -> not trivial, but there are easy O(nlogn) and O(nlog^2n) algorithms
2) construct an lcp array O(n) -> trivial (there is also a trivial O(nlogn) one).
3) construct an RMQ data structure: O(n) construction and O(1) querying -> not trivial (there are trivial O(nlogn) construction and O(logn) query ones)
4) Iterate over every position i in the original string S1. Find the complement position in S2 in the generalized string. Find the longest common prefix: O(1)

In general, the mentioned approach must be modified for even and odd length palindromes. The distinction is that in the odd length palindrome you just introduce a gap when selecting the indices.
This yields an O(n) solution to the problem.

Regarding the article:
The author mentions that finding the longest common substring is not enough since the two substrings with such lcp may not be neighbours in the original string.
Therefore, we want to find two strings A and B, one belonging to S1 and one to S2, such that lcp(A,B) is largest, but also A . rev(B) is in the original S1.

I hope I have been clear enough.

Answer 2

I am just starting out with leetcode and came across the aforementioned article.

Tried to implement the exact same logic. Was successful but it is not much efficient than the DP solution mentioned Longest palindromic substring | Dynamic programming

You can simply check whether the ranges are equal to implement the logic in the algorithm.

Here is my solution implementing the article. Takes a runtime of 364 ms, which is just faster than 21.99% of C++ online submissions

    class Solution {
public:
    string longestPalindrome(string s) {
        int max = 0,temp,mr=0;
        string revs = s;
        reverse(revs.begin(), revs.end());
        string soln;
        int l = s.size();
        if(l==0 || l==1) return s;
        
        int dp[l+1][l+1];
        
    
        
            for(int row = 0; row < l; row ++)
            for(int col = 0; col < l; col ++){
                if(s.at(row) != revs.at(col))
                    dp[row+1][col+1] = 0;
                else{
                        
                        if(row==0 or col ==0) temp = 1;
                        else temp = dp[row][col] + 1;
                        dp[row+1][col+1] = temp;
                        if(temp > max && row-temp+1 == l-col -1 && l-row -1 == col-temp +1 ){
                                mr = row;max = temp;
                            } 
                        }
                }
       
        /*        for(int row = 0; row < l+1; row ++){
            for(int col = 0; col < l+1; col ++){
                if(row == 0 && col > 0)
                    cout << revs.at(col-1) << ", ";
                else if(col == 0 && row > 0)
                        cout << s.at(row-1) << ", ";
                else
                cout << dp[row][col] << ", ";
            }
            cout << endl;
        }

       cout << "\n___________\nmax:" << max <<"\nmr: " << mr << "\n"; */
        //return (max>1)?s.substr(mr-max+1,max):s.substr(0,1);
        return s.substr(mr-max+1,max);
    }
};

Answer 3

I am stuck there, so I google to reach here. Now I understand.Let me take original String which the author mentioned as a example.

S = "caba', S' = "abac", so longest common substring is aba.

The sentence is "we check if the substring’s indices are the same as the reversed substring’s original indices."

1.What is the substring’s indices?

"aba" is [1, 2, 3]

2.what is reversed substring’s original indices? Reversed substring is "aba", and its original indices is also [1, 2, 3].

So that answer is correct.

And we are looking at another example.

S="abacdfgdcaba", S' = "abacdgfdcaba", so longest common substring is "abacd".

So same process:

1.What is the substring’s indices?

"abacd" is [0, 1, 2, 3, 4].

2.what is reversed substring’s original indices? Reversed substring is "abacd", but its original indices is also [7, 8, 9, 10, 11]. So These two "abacd" is not same one, the answer is not correct.

I think that sentence is a bit tricky, and I think the author made it a little hard to understand. ​

I think the sentence should be changed to "To rectify this, each time we find a longest common substring candidate, we check if the substring are the same one as the reversed substring’." ​

Answer 4

In case someone is looking for an implementation of the this question, where we use Longest Common Substring to find the Longest Palindromic Substring, this is my version of it.

package leetcodeproblems;

/**
 * Created by Nandan Mankad on 23-11-19.
 */
public class LongestPalindromicSubstring {
    public static void main(String[] args) {
        /*String s = "aacdefcaa";*/
        /*String s = "dabcbae";*/
        /*String s = "babad";*/
        /*String s = "cbbd";*/
        /*String s = "cbbc";*/
        String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        System.out.println(longestPalindrome(s));
    }

    public static String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        StringBuilder sb = new StringBuilder(s);
        String revString = sb.reverse().toString();  // Reversing the string - to compute LCS.
        int dp[][] = new int[s.length() + 1][s.length() + 1];
        int maxLength = 0;
        int iPos = 0;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp.length; j++) {
                if (s.charAt(i - 1) == revString.charAt(j - 1)) { // Character matches in Original String and Reversed String.
                    dp[i][j] = dp[i - 1][j - 1] + 1;              // Standard Longest Common Substring logic for Original and Reversed String.
                    int revIdx = i;
                    int forIdx = j - dp[i][j] + 1;
                    if (s.length() - revIdx + 1 == forIdx) {      // Here we check if the reverse string original idx is same as original string idx.
                        if (maxLength < dp[i][j]) {
                            maxLength = dp[i][j];
                            iPos = i;
                        }
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }

        StringBuilder res = new StringBuilder();
        while (maxLength > 0) {
            res.append(s.charAt(iPos- 1));
            maxLength--;
            iPos--;
        }

        return res.toString();
    }
}

Link

It passes all the testcases on Leetcode for the problem. Improvisations might be possible where we iterate the string in reverse and not reverse the actual string, etc.

Time Complexity: O(N^2) Space Complexity: O(N^2)