Valid Palindromic Sequence — Problem Statement & Solution Guide
Problem Description
Given a string sequence, determine if it is possible to obtain a palindrome by removing at most one character.
Examples
Input
aba
Output
false
Explanation: The input string 'aba' is already a palindrome, so no removal is needed. Therefore, the output should be false.
Input
abca
Output
false
Explanation: Removing 'c' from 'abca' results in 'aba', which is a palindrome. However, the problem statement asks for at most one removal, and removing 'c' is not the only possible solution. Another possible solution is to remove 'a' from 'abca'. Therefore, the output should be false.
Constraints
- 1 <= s.length <= 10^5
- s consists of lowercase English letters.
Optimal Approach & Strategy
Two pointers. When s[left] != s[right], check if substring(left+1, right) is palindrome OR substring(left, right-1) is palindrome. Time O(N), Space O(1).
Brute Force Approach
Remove each character one by one and check if string becomes palindrome. Time O(N^2).
Verified Code Solutions
function validPalindromicSequence(sequence) { if (sequence.length < 2) return true; let left = 0, right = sequence.length - 1; while (left < right) { if (sequence[left] !== sequence[right]) { if (sequence[left + 1] === sequence[right]) { left++; } else if (sequence[left] === sequence[right - 1]) { right--; } else { return false; } } else { left++; right--; } } return true; }class Solution {
public boolean validPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
}
left++, right--;
}
return true;
}
private boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++, right--;
}
return true;
}
}def valid_palindrome(s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return (s[left + 1:right + 1] == s[left + 1:right + 1][::-1] or s[left:right] == s[left:right][::-1])
left, right = left + 1, right - 1
return Truefunction validPalindromicSequence(sequence) { if (sequence.length < 2) return true; let left = 0, right = sequence.length - 1; while (left < right) { if (sequence[left] !== sequence[right]) { if (sequence[left + 1] === sequence[right]) { left++; } else if (sequence[left] === sequence[right - 1]) { right--; } else { return false; } } else { left++; right--; } } return true; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.