Check string for palindrome with one deletion

by linkjobai

HTML

<style>body{font-family:system-ui,sans-serif;max-width:760px;margin:2rem auto;padding:0 1rem;line-height:1.6}pre{background:#f4f4f4;color:#000;padding:1rem;overflow:auto}</style>
<h1>Valid Palindrome II (LeetCode 680): One Allowed Deletion</h1>
<p>Given a string <code>s</code>, return true if it can become a palindrome after deleting at most one character. The brute force tries every deletion and checks each result, which is O(n&sup2;). The two-pointer version is O(n).</p>
<h2>Idea</h2>
<p>Walk two pointers inward from both ends. While the characters match, keep going. At the first mismatch you have exactly two choices: skip the left character or skip the right one. Check whether either remaining slice is a plain palindrome. You never need a second branch, because only one deletion is allowed.</p>
<pre>function validPalindrome(s) {
  const isPal = (i, j) =&gt; {
    while (i &lt; j) { if (s[i] !== s[j]) return false; i++; j--; }
    return true;
  };
  let i = 0, j = s.length - 1;
  while (i &lt; j) {
    if (s[i] !== s[j]) return isPal(i + 1, j) || isPal(i, j - 1);
    i++; j--;
  }
  return true;
}
console.log(validPalindrome("abca")); // true
console.log(validPalindrome("abc"));  // false</pre>
<h2>Interview notes</h2>
<ul><li>Time O(n), space O(1): each branch scans at most the remaining window once.</li>
<li>A common bug is only trying one side at the mismatch; "cupuufuc"-style inputs need the other side.</li>
<li>Follow-up: with k deletions allowed, it becomes a longest-palindromic-subsequence DP (LeetCode 1216).</li></ul>
<p>Disclosure: I build <a href="https://www.linkjob.ai/coding-interview-copilot/">an AI coding interview copilot</a> at Linkjob AI, and I write these notes while practicing classic problems.</p>