How to Solve Valid Palindrome
Valid Palindrome Introduction
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
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
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;
}1function isPalindromeWithOneCharRemoved(string) {
2 if (!string) {
3 return true;
4 }
5
6 let n = string.length;
7 let i = 0;
8 let j = n - 1;
9
10 while (i < j) {
11 if (string.charAt(i) !== string.charAt(j)) {
12 // check if removing either i-th or j-th character makes string a palindrome
13 return isPalindrome2(string, i, j - 1) || isPalindrome2(string, i + 1, j);
14 }
15 i++;
16 j--;
17 }
18
19 // string is already a palindrome
20 return true;
21}
22
23function isPalindrome2(string, start, end) {
24 while (start <= end) {
25 if (string.charAt(start) !== string.charAt(end)) {
26 return false;
27 }
28 start++;
29 end--;
30 }
31 return true;
32}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.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
