Home > Mobile >  Find out longest palindromic substring
Find out longest palindromic substring

Time:05-04

I want to run this code and I am getting aba but not bab. How can I get the solution from this code? Suggestions with explanations so that I can understand properly.

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
var longestPalindrome = function(s) {
    let splitString = s.split("");
    let reverse = splitString.reverse()
    console.log(reverse)
    let check_value = s.split("")
    console.log(check_value)
    let store = []
    check_value.map((x,id) => {
        if(x == reverse[id]){
            store.push(x)
        }
    })
    console.log(store)                               
};

CodePudding user response:

Your function is not doing the job right. It assumes that the center of the palindrome is always in the center of the input string. So that explains why "bab" is not found.

But even worse, it will even give false positives.

For instance:

Input: "dobad"
Output: ["d", "b", "d"]

So you'll need to revisit the code challenge. The approach you had in mind is not the right one.

If you cannot find how to do it, have a look at Longest palindromic substring on Wikipedia. Also on this site there are several Q&A on the subject.

CodePudding user response:

So, you have these letters in the arrays: check_value => 0: b, 1: a, 2: b, 3: a, 4: d reverse => 0: d, 1: a, 2: b, 3: a, 4: b

And in your algorithm, you are doing

First step:

  • x = b
  • id = 0
  • reverse[id] = d x != d then the value is not saved

Second step:

  • x = a
  • id = 1
  • reverse[id] = a x == a then the value is saved
  • store = [a]

And so on, so that is the reason why the algorithm is not working

A tip, iterate the string and find the next index of the current character, so, if the character is b find the indexes of any other b in the same array and validate if the substring generated between the current character index and the found indexes is a palindrome

  • Related