How do you solve Valid Palindrome II?

Use two pointers l and r starting at the string's ends. Move inward while characters match. On mismatch, check if either substring s[l+1:r+1] or s[l:r] is a palindrome using a helper function. Return true if either is true; otherwise, false. If no mismatch occurs, return true.

Valid Palindrome II

Q: What is the time complexity of Valid Palindrome II?

O(n). The main loop runs once from both ends inward, and at most two additional palindrome checks on substrings are performed, each linear in length, resulting in overall O(n) time.

Q: What pattern does Valid Palindrome II use?

The Pattern: Two Pointers (Greedy with Conditional Branching) The Heuristic: When verifying a palindrome with a limited number of allowed deletions, use two pointers to detect the first mismatch and then greedily check the two possible substrings formed by skipping one character, ensuring linear time complexity.

Easy Two Pointers

Problem

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

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters.

Example

Input: s = "abca"

Output: true

The string "abca" is not a palindrome, but by deleting the character 'c' at index 2, it becomes "aba", which is a palindrome. The algorithm uses two pointers starting at the ends of the string and moves inward. When a mismatch is found, it tries skipping either the left or right character to check if the remaining substring is a palindrome. This conditional deletion check is the critical moment that enables the solution to handle the 'at most one deletion' constraint efficiently.

Approach

Straightforward Solution

A brute-force approach tries deleting each character and checking if the resulting string is a palindrome, resulting in O(n^2) time, which is inefficient for large strings.

Core Observation

A palindrome reads the same forwards and backwards. Using two pointers from the ends inward allows linear-time verification. The challenge is to allow at most one character deletion to fix a mismatch.

Path to Optimal

Preview

The key insight is that when a mismatch occurs between characters at pointers l and r, only two substrings need checking: skipping the left character or skipping the right character. If either substring is a palindrome, the answer is true…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use two pointers l and r starting at the string's ends. Move inward while characters match…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The main loop runs once from both ends inward, and at most two additional palindrome checks on substrings are performed, each linear in length, resulting in overall O(n) time.

Space

O(1)

Only a few integer pointers and variables are used; no additional data structures proportional to input size are allocated.

Pattern Spotlight

Two Pointers (Greedy with Conditional Branching)

When verifying a palindrome with a limited number of allowed deletions, use two pointers to detect the first mismatch and then greedily check the two possible substrings formed by skipping one character, ensuring linear time complexity.

Solution

Python

1class Solution:
  def validPalindrome(self, s: str) -> bool:
3
      def isPalindrome(l, r):
          while l < r:
              if s[l] != s[r]:
                  return False
              l += 1
              r -= 1
          return True
11
      l = 0
      r = len(s) - 1
14
      while l < r:
16
          if s[l] != s[r]:
              return (
                  isPalindrome(l + 1, r) or
                  isPalindrome(l, r - 1)
              )
22
          l += 1
          r -= 1
25
      return True

Step-by-Step Solution

Verify Palindromic Substrings with Two Pointers

4def isPalindrome(l, r):
  while l < r:
      if s[l] != s[r]:
          return False
      l += 1
      r -= 1
  return True

Objective

To check if a substring defined by indices l and r is a palindrome by comparing characters inward.

Key Insight

A palindrome check can be efficiently performed by two pointers moving inward from the substring boundaries. This helper function enables quick verification of candidate substrings after a mismatch, avoiding repeated full scans.

Interview Quick-Check

Core Logic

The helper function uses two pointers to compare characters from both ends, returning false immediately on mismatch, ensuring O(n) time.

State & Boundaries

The loop continues while l < r, ensuring all character pairs are checked without overlap.

Common Pitfalls & Bugs

Failing to return false immediately on mismatch leads to incorrect palindrome verification.

Traverse String with Two Pointers and Handle Mismatch

To iterate from both ends of the string, detect the first mismatch, and attempt to fix it by skipping one character.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 4 Critical

def isPalindrome(l, r):

Define a helper function that checks whether the substring between indices l and r is a palindrome.

A helper function isolates the palindrome verification logic so it can be reused when testing substrings after a mismatch.

Line 5 Critical

while l < r:

Start a loop that compares characters symmetrically while the pointers have not crossed.

Two pointers moving inward is the most efficient way to verify the palindrome property in linear time.

Full line-by-line criticality + rationale for all 18 lines available on Pro.

Test Your Understanding

Why is it sufficient to check only the two substrings formed by skipping one character at the first mismatch?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Valid Palindrome II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Valid Palindrome II drill

or drill a free problem

1	`class Solution:`
2	`def validPalindrome(self, s: str) -> bool:`
3
4	`def isPalindrome(l, r):`
5	`while l < r:`
6	`if s[l] != s[r]:`
7	`return False`
8	`l += 1`
9	`r -= 1`
10	`return True`
11
12	`l = 0`
13	`r = len(s) - 1`
14
15	`while l < r:`
16
17	`if s[l] != s[r]:`
18	`return (`
19	`isPalindrome(l + 1, r) or`
20	`isPalindrome(l, r - 1)`
21	`)`
22
23	`l += 1`
24	`r -= 1`
25
26	`return True`

4	`def isPalindrome(l, r):`
5	`while l < r:`
6	`if s[l] != s[r]:`
7	`return False`
8	`l += 1`
9	`r -= 1`
10	`return True`