Can it be done by reversing the string and finding the longest substring with itself?


  • 1
    N

    From the leetcode blog, one of the methods of solving this is:

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

    Reverse S and become S’. Find the longest common substring between S and S’, which must also be the longest palindromic substring.
    This seemed to work, let’s see some examples below.

    For example,
    S = “caba”, S’ = “abac”.
    The longest common substring between S and S’ is “aba”, which is the answer.

    Let’s try another example:
    S = “abacdfgdcaba”, S’ = “abacdgfdcaba”.
    The longest common substring between S and 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 S. 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.

    Is this part correct?

    example string: abcxycba
    reverse string: abcxycba

    The substring indices are same as reversed string original indices and yet it is not a palindrome?


  • 1
    M

    Not quite. What is being compared is not the indices in the reversed string, but where that string would be in the original. In your example, you would have common substrings at [0,2] for each string, but the reversed substring's original indices for that substring would be [5,7]. The substring at the proper place would be "cba", which is non-equal. The same thing happens with "cba", just with the indices swapped.

    To get the original indices, for [a,b] in the reversed string, the original indices are [len-b-1, len-a-1].


  • 0
    N

    Could you explain which example string are you working with. I cant understand how you got cba


  • 0
    M

    The example string I am using is the string you offered, "abcxycba". The algorithm looks for the same substring occurring, but it needs to occur in the right place as well. The formula above gives a way of determining the original indices, which must be the indices where the string occurs in the original string. In your example, the substring abc occurs at he first three characters in the original string, and the first three in the reversed string. The algoritm you are examining required both sets of indices to be the same place in the original string, so you need to convert the reversed strings indices to their original position, which is the last three. My offering of cba was to show the contents of the substring that did map to the correct location.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.