Valid Palindrome II Easy 0 attempts
LeetCode ↗

Valid Palindrome II

Easy StringHash Table LeetCode

Given a string s, return true if it can become a palindrome after deleting at most one character.

The string only contains lowercase letters. If it's already a palindrome, return true as well (zero deletions is valid).

Examples

Input: s = "aba"
Output: true

Input: s = "abca"
Output: true
Explanation: Removing 'b' gives "aca", or removing 'c' gives "aba" — both palindromes.

Input: s = "abc"
Output: false

Constraints

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters.
Sample Input
s = "abca"
Sample Output
true
Constraints
  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters
Test Cases
Case 1
Args: ["abca"] Expected: true
Topics
StringHash Table

Use two pointers from both ends moving inward. When a mismatch is found, try skipping either the left or right character and check if the remaining substring is a palindrome. If either works, return true.

function validPalindrome(s) {
  function isPalin(left, right) {
    while (left < right) {
      if (s[left] !== s[right]) return false;
      left++;
      right--;
    }
    return true;
  }

  let left = 0, right = s.length - 1;
  while (left < right) {
    if (s[left] !== s[right]) {
      return isPalin(left + 1, right) || isPalin(left, right - 1);
    }
    left++;
    right--;
  }
  return true;
}

Time: O(n) — each character is visited at most twice. Space: O(1) — no extra data structures.

Saved in this browser only. Private to you.

JavaScript