Two pointers pattern to solve palindrome problem

May 17, 2023

I want to solve the "palindrome" problem by using the ‘two pointers’ pattern. Here is the code that solves this problem:

var isPalindrome = function(s) {
    const newStr = s.toLowerCase().replace(/[^0-9a-z]/g, "")

    let left = 0
    let right = newStr.length-1
    
    while (left < right) {
        if (newStr[left] !== newStr[right]) {
            return false
        }

        left++
        right--
    }

    return true
};

console.log(isPalindrome('racecar'))
console.log(isPalindrome('Ceci n’est pas une palindrome'))

The above code is working as expected, but the problem is that I do not quite understand how this logic is working:

while(left < right)

Ensures the correct work to solve the palindrome problem. Say, we have this string ‘racecar’ and if we move left and right pointers to each other and if both pointers get to both of the ‘c’ next to ‘e’ then while loop will run LAST time but we miss ‘e’ and because we miss ‘e’ how can we be sure that two pointers solves palindrome problem? Can someone please clarify this?

I do not understand how two pointers pattern solve palindrome problem is we miss ‘e’ considering we have this string ‘racecar’.

>Solution :

Now there can be two cases for the input.

Input is even in length
Input is odd in length

while(left < right) means that we have to check until the left pointer crosses the right pointer. Before it does if at any moment the letters are not same at left and right pointer, the input is not palindrome.

now, when the input length is odd, you can just ignore the middle element since it does not have any counter match.

If you want to explicitly check if arr[middle]==arr[middle] just include the equality in the while condition. while(left<=right)