Write a function that takes a string as input and checks whether it can be a valid palindrome by removing at most one character from it.

Constraints:

• $1 \leq$ string.length $\leq$ $10^5$

• The string only consists of English letters.

The algorithm uses a two pointer technique to determine whether a string is a palindrome or can be transformed into it by removing at most one character, where one pointer starts at the beginning and the other at the end. As the pointers move toward each other, they compare the corresponding characters. If all pairs match, the string is a palindrome. However, if a mismatch is detected, the algorithm explores two possibilities: removing the character at either pointer and checking if the resulting substring forms a palindrome. If either check passes, the function returns TRUE; otherwise, it returns FALSE.

The algorithm consists of two functions:

• is_substring_palindrome(string, left, right): This helper function checks if a substring of the input string, defined by left and right indexes, is a palindrome. It uses a two-pointer approach, comparing characters from both ends inward. If any mismatch is found, it returns FALSE; otherwise, it returns TRUE.

• is_palindrome(string): This function checks if the entire string is a palindrome or can become one by removing one character. It initializes two pointers, left_index at the start and right_index at end of the string:

  • If the characters at the left_index and right_index are the same, it moves both pointers inward.

  • If the characters differ, it checks two cases by calling is_substring_palindrome:

    • The substring from left_index + 1 to right_index

    • The substring from left_index to right_index - 1

  • If either case returns TRUE, the function returns TRUE; otherwise, it returns FALSE.

If the traversal completes without finding a mismatch, the string is a palindrome, and the function returns TRUE.

The slides below illustrate how we would like the algorithm to run: