easyTwo PointersPattern: Two Pointers
Valid Palindromic Sequence Solution
Problem Statement
Given a string `sequence`, determine if it is possible to obtain a palindrome by removing at most one character.
Examples
Example 1:
Input:aba
Output:true
Explanation: aba is already a palindrome
Example 2:
Input:abca
Output:true
Explanation: removing 'c' makes it a palindrome
Example 3:
Input:abc
Output:false
Explanation: cannot become a palindrome by removing one character
Constraints
- 1 <= s.length <= 10^5
- s consists of lowercase English letters.
Time: O(N) Space: O(1)
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).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.