EASY
DATA STRUCTURES AND ALGORITHMS

# How to Solve Valid Palindrome

Written By ## 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 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

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

• Time Complexity: O(N), where N is the length of the input string, because we loop through the string only once.
• Space Complexity: O(1), because we don't use any data structures that grow with the size of the input.