Valid Palindrome (Interview Solution)

How to Solve Valid Palindrome

Valid Palindrome Introduction

The Valid Palindrome question involves determining if this string, after removing any one character, can become a palindrome, and if so returning true, otherwise returning false. The challenge in this problem is designing the loop to check if removing a character from the start of the end will turn the string into a palindrome.

Valid Palindrome Problem

Determine if this string, after removing any one character, can become a palindrome. If possible, return true; otherwise, return false.

Example Inputs and Outputs

Example 1

Input: s = "aba"

Output: True

Example 2

Input: s = "abca" Output: True

Example 3

Input: words = "abc"

Output: False

Valid Palindrome Solutions

The isPalindromeWithOneCharRemoved function takes a string input and returns True if the input string can be made into a palindrome by removing at most one character. The function first checks if the input string is empty or has a length of one or two, in which case it must already be a palindrome and returns True in those cases. Otherwise, it uses two pointers to traverse the string from both ends, checking if the characters at each position match. If a mismatch is found, the function checks if removing either the left or right character would make the remaining substring a palindrome by calling the isPalindrome2 helper function. If either of these substrings is a palindrome, the function returns True. If the entire string is already a palindrome, the function also returns True. Otherwise, it returns False.

The isPalindrome2 helper function takes a string and two pointers indicating the start and end positions of a substring. It then uses two pointers to traverse the substring from both ends, checking if the characters at each position match. If a mismatch is found, the function returns False. If the entire substring is traversed without finding a mismatch, the function returns True, indicating that the substring is a palindrome.

function isPalindromeWithOneCharRemoved(string) {
    if (!string) {
        return true;
    }

let n = string.length;
    let i = 0;
    let j = n - 1;

while (i < j) {
        if (string.charAt(i) !== string.charAt(j)) {
            // check if removing either i-th or j-th character makes string a palindrome
            return isPalindrome2(string, i, j - 1) || isPalindrome2(string, i + 1, j);
        }
        i++;
        j--;
    }

// string is already a palindrome
    return true;
}

function isPalindrome2(string, start, end) {
    while (start <= end) {
        if (string.charAt(start) !== string.charAt(end)) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

Time/Space Complexity Analysis