Having a tough time understanding longestPalindrome algorithm

Question

I found this solution to make sense to an algorithm question about finding the longest palindrome in a substring. However, I am struggling to understand what the expand function is actually doing. I thought it would run from the center, but console logging is showing that it is run for the whole string. I am having difficulty understanding why it's entering the while loop for any character that's not the same as s[begin] === s[end] that's what I thought this line was preventing. I am not sure why expand is called twice either. Also, why do we add begin + 1 rather than just begin when returning the substring. The code is below. Any clarification of how the expand works would be appreciated.

var longestPalindrome = function (s) {
    //either when empty string or is a single character
    if (!s || s.length <= 1) return s

    let longest = s.substring(0, 1)

    for (let i = 0; i < s.length; i++) {
        let temp = expand(s, i, i, 'first')
        // console.log(temp, 'i am the first')
        if (temp.length > longest.length) {
            longest = temp
        }
        temp = expand(s, i, i + 1, 'second')
        // console.log(temp, 'i am the second')
        if (temp.length > longest.length) {
            longest = temp
        }
    }
    return longest
}

const expand = (s, begin, end, counter) => {
    while (begin >= 0 && end <= s.length - 1 && s[begin] === s[end]) {
        console.log(s, 'i am string')
        console.log(begin, 'i am begin')
        console.log(end, 'i am begin')
        console.log(s[begin], s[end])
        console.log(counter)
        begin--
        end++
    }
    return s.substring(begin + 1, end)
}

console.log(longestPalindrome('cbbd'))
console.log(longestPalindrome('babad'))
console.log(longestPalindrome('ac'))
console.log(longestPalindrome('abb'))

Answer 1

However, I am struggling to understand what the expand function is actually doing. I thought it would run from the center, but console logging is showing that it is run for the whole string

Palindromes can be of two types
1. Even length palindromes e.g. - "abba"
2. Odd length palindromes e.g. - "aba"

Now, each index of the given string can be center of either of these types of palindromes. So, every index of the string is tested for this possibility.

longestPalindrome function takes the string and for each index of the string it tests that index as center of an odd length palindrome and an even length palindrome.

expand function takes the two center indices and begins expanding them outwards. For an odd length palindrome, the center character should be compared with itself. So, expand is called with both begin and end as same index.

I am having difficulty understanding why it's entering the while loop for any character that's not the same as s[begin] === s[end] that's what I thought this line was preventing.

The longestPalindrome will send the two indices such that this condition s[begin] === s[end] is not true but the while loop will check and not expand them further. You can prevent this functionality from the longestPalindrome function if you want to.

I am not sure why expand is called twice either.

It is because of the two types of palindromes on the basis of their length. You need to test for both these types.

Also, why do we add begin + 1 rather than just begin when returning the substring.

It is because begin is one off when if comes out of the while loop. You can do a simulation on paper to understand better.

Answer 2

Well, let's say we want to find the palindrome of s when s = 'abba'.

note: Think of expansion as a palindrome finder that takes in the center index. Keep in mind that I'll explain how does expansion work afterwards

We'll shift the center of the expansion from 0 to 3(the final index). First, it checks the the expansion from begin = 0 and end = 0.

s = 'abba'

If begin = 0 and end = 0, expansion returns 'a'.

v___
abba //only the palindrome from 0 is 'a'

If begin = 0 and end = 1, expansion returns ' '.

_v___
a bba //there are no palindrome from between 0 and 1 

If begin = 1 and end = 1, expansion returns 'b'.

_v__
abba //only the palindrome from 1 is 'b'

If begin = 1 and end = 2, expansion returns 'abba'.

__v__
ab ba //the palindrome from between b and b is 'abba'

If begin = 2 and end = 2, expansion returns 'b'.

If begin = 2 and end = 3, expansion returns ' '.

If begin = 3 and end = 3, expansion returns 'a'.

At this point, we've tested all the possible palindrome of s. Finally, the code returns the longest palindrome so far, which will be 'abba' in this case.

Notice why we need to perform expansion twice. At i = 1, we can look for a palindrome from the center.

_v__
abba

But also from the place between b and b

__v__
ab ba

Former returns 'b' while latter returns 'abba'. This is why you need to perform 2 expansions for each i.

---

Now, what exactly happens inside the expand function? Let's use the example. s = 'aacdeedcba', and begin = 4 and end = 5.

First, the while loop checks if s[begin] == s[end].

____vv____
aacdeedcba

Obviously 'e' === 'e' is true, so we'll shift begin to left side, and end to right side .

Again we'll check if s[begin] === s[end].

___v__v____
aacdeedcba

Again, 'd' === 'd' is true, so we'll shift begin to left side, and end to right side .

we'll check again.

__v____v__
aacdeedcba

Again, 'c' === 'c' is true, so we'll shift begin to left side, and end to right side .

we'll check again.

_v______v_
aacdeedcba

This time, 'a' === 'b' is not true. So the while loop is stopped. And the expansion function returns 'cdeedc'.