Valid Palindrome II Easy 0 attempts
LeetCode ↗

Valid Palindrome II

Easy StringHash Table LeetCode

You're given a string s. Report true if removing no more than one character from it can turn it into a palindrome.

The string is made up solely of lowercase letters, and a string that's already a palindrome also counts — you're allowed to delete zero characters.

Input Format
Implement validPalindrome(s). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
s = "abca"
Output
true

Example 2

Input
s = "abc"
Output
false
Constraints
  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters
Test Cases (2)
Case 1
Args: ["abca"] Expected: true
Case 2
Args: ["abc"] Expected: false
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.

javascript
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