Skip to main content

680. Valid Palindrome II

easyAsked at Meta

Given a string, return true if you can make it a palindrome by deleting at most one character. Meta asks this to test whether you can adapt the two-pointer palindrome check to branch on a single mismatch without recursing or losing O(n) time.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Meta loops.

  • Glassdoor (2026-Q1)— Meta E4/E5 onsite reports cite this as a recurring favorite.
  • Blind (2025-12)— Recurring Meta interview problem flagged as a 'Meta-loves-this-one' string problem.

Problem

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

Constraints

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters.

Examples

Example 1

Input
s = "aba"
Output
true

Example 2

Input
s = "abca"
Output
true

Explanation: You could delete the character 'c'.

Example 3

Input
s = "abc"
Output
false

Approaches

1. Try every single deletion + palindrome check

For each index i, build the string without s[i] and check palindrome-ness.

Time
O(n^2)
Space
O(n)
function validPalindromeBrute(s) {
  function isPal(str) {
    let l = 0, r = str.length - 1;
    while (l < r) { if (str[l] !== str[r]) return false; l++; r--; }
    return true;
  }
  if (isPal(s)) return true;
  for (let i = 0; i < s.length; i++) {
    if (isPal(s.slice(0, i) + s.slice(i + 1))) return true;
  }
  return false;
}

Tradeoff: Quadratic; will TLE at the upper bound. Mention only to anchor the optimal.

2. Two-pointer with single-deletion branch (optimal)

Two pointers. On the first mismatch, try skipping either the left or right char and check palindrome on the remainder.

Time
O(n)
Space
O(1)
function validPalindrome(s) {
  function isPalRange(l, r) {
    while (l < r) { if (s[l] !== s[r]) return false; l++; r--; }
    return true;
  }
  let l = 0, r = s.length - 1;
  while (l < r) {
    if (s[l] !== s[r]) {
      return isPalRange(l + 1, r) || isPalRange(l, r - 1);
    }
    l++;
    r--;
  }
  return true;
}

Tradeoff: Linear. On a mismatch, try BOTH skip-left and skip-right — only one will be valid if a single deletion fixes the string. Logarithmically, this is still O(n) because the inner palindrome check is bounded by the remaining range.

Meta-specific tips

Meta interviewers grade this on the 'try both branches' insight. State out loud: 'When I hit a mismatch, I don't know which char to delete — left or right. So I try both and return true if either works.' Without that articulation, candidates often try only the left skip and fail on cases where the right skip is the answer.

Common mistakes

  • Trying only the left skip OR only the right skip (you must try both).
  • Using slice or splice to mutate the string — O(n) per call defeats the purpose.
  • Forgetting to first run the standard palindrome check before branching.

Follow-up questions

An interviewer at Meta may pivot to one of these next:

  • What if you could delete up to K characters?
  • What if you could also INSERT characters?
  • Find the minimum number of deletions to make a string a palindrome.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is this O(n) and not O(n^2)?

The first pass through both pointers is O(n). On a mismatch, we branch into two inner palindrome checks — each is at most O(n - 2). Total work: O(n) + O(n) = O(n).

Can both branches succeed in different cases?

Yes — depending on the string. We don't care which one succeeded, just that at least one did.

Practice these live with InterviewChamp.AI

Drill Valid Palindrome II and other Meta interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →