AlgoMaster Logo

Valid Palindrome II

easyFrequency4 min readUpdated August 19, 2026

Understanding the Problem

We need to determine whether a string is "almost" a palindrome. That means it either already reads the same forwards and backwards, or it can become one by removing at most one character.

One way to solve this is to remove each character one at a time and check whether the result is a palindrome. With strings up to 100,000 characters, that is too slow. A faster idea: scan from both ends with two pointers. While the mirrored characters match, move inward. At the first mismatch, exactly one of two characters must be the one we delete, the one at the left pointer or the one at the right pointer. Check whether skipping either one leaves a palindrome. If so, the answer is true; if neither works, no single deletion can fix the string.

Key Constraints:

  • 1 <= s.length <= 10^5 → A solution that tries every deletion does up to n palindrome checks of O(n) each, which is 10^10 operations for the largest input. That rules out the O(n^2) approach and pushes toward O(n).
  • s consists of lowercase English letters → Comparisons are plain character equality, with no case folding or skipping of non-alphanumeric characters.

Approach 1: Brute Force

Intuition

Try deleting each character one at a time and check whether the resulting string is a palindrome. If any deletion produces a palindrome, return true. A string that is already a palindrome also returns true, since deleting any one of its characters when it has matching pairs, or zero characters, still satisfies the "at most one" rule.

For each of the n possible deletions, the palindrome check is O(n), so the total work is O(n^2).

Algorithm

  1. If s is already a palindrome, return true without deleting anything.
  2. For each index i from 0 to n - 1:
    • Create the string with the character at index i removed.
    • Check if this new string is a palindrome.
    • If it is, return true.
  3. If no single deletion produces a palindrome, return false.

The problem allows deleting at most one character, so a string that is already a palindrome qualifies without any deletion. Step 1 handles that case directly. The loop would also catch it, since deleting one character from a matching pair leaves the rest symmetric, but checking first avoids building n candidate strings to rediscover an answer we already have.

Visualization and Code

Loading animation...

This is too slow for strings up to 100,000 characters. The next approach avoids redundant deletions by only examining the one position where a deletion could matter.

Approach 2: Two Pointers (Greedy)

Intuition

Start two pointers at both ends of the string and move them inward while the mirrored characters match. At the first mismatch, the single allowed deletion has to remove either the left character or the right one, because keeping both would leave a pair that can never match. So check two substrings: s[left+1..right] (delete the left character) and s[left..right-1] (delete the right character). If either is a palindrome, the answer is true. If neither is, no single deletion can fix the string.

Algorithm

  1. Initialize two pointers: left = 0 and right = s.length - 1.
  2. Move them inward while s[left] == s[right].
  3. If we reach left >= right without a mismatch, the string is already a palindrome. Return true.
  4. At the first mismatch, check two options:
    • Is s[left+1..right] a palindrome? (skip left character)
    • Is s[left..right-1] a palindrome? (skip right character)
  5. Return true if either option is a palindrome, false otherwise.

Visualization and Code

Loading animation...