Longest palindrome in a string

Actually, yes, in this case you don't need to shift anything, specially not where you were doing it. Instead, you want to start comparing from a different place.

Let's see what it is you want to do: You have the string "zxzxbaabcd" and reversed "dcbaabxzxz". The general algorithm (leaving aside other details you still need to solve) is this:

Place the strings in a starting position:

 zxzxbaabcd
 ^^^^^^^^^^
 ||||||||||
 vvvvvvvvvv
 dcbaabxzxz

Given this position, loop through the strings comparing. But just loop comparing, no need to shift or reposition the strings.

Now, you reposition one of the strings:

 zxzxbaabcd
 ^^^^^^^^^^
 ||||||||||
 vvvvvvvvvv
  dcbaabxzxz

And repeat the loop comparing. Move one more position again, then loop again. etc. So, you're actually doing something like this:

external loop i {
    displace one position;
    reset the counter to zero;
    internal loop j {
        if s[j] === r[j] increase the counter;
        else { 
            if the counter is bigger than the previous time, then keep it.
            in any case, reset the counter to zero;
        }
    }
}

Now, be aware of a couple of things. With the counter, you are only keeping track of how long is the current candidate palindrome, but not what the palindrome itself is. So, if you want to find not 4 but actually "baab" then you'll need to keep track of that too instead of just using a counter.

Also, you should be aware there's another flaw in your algorithm: The starting position should not be:

"zxzxbaabcd"
 ^^^^^^^^^^
 ||||||||||
 vvvvvvvvvv
"dcbaabxzxz"

But instead, it should be:

          zxzxbaabcd
          ^^^^^^^^^^
          ||||||||||
          vvvvvvvvvv
 dcbaabxzxz

Oh, and how do you position the strings like that? Not by shifting (pulling out one element) one of the strings, that is a destructive operation. You can do it in various ways instead. The easiest way is to use the index of the outer loop as an offset or displacement (i.e. compare s[i] to r[j+i]). Ah, and of course: displace just on one of the strings/arrays, not both.

/r/javascript Thread Parent