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.

Valid Palindrome II - LeetCode Solution

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.

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

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. This reduces the problem to O(n) time by performing at most two palindrome checks on substrings.

Optimal Approach

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.

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.

Solution

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

1

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.

2

Traverse String with Two Pointers and Handle Mismatch

12l = 0
13r = len(s) - 1
15while l < r:
17    if s[l] != s[r]:
18        return (
19            isPalindrome(l + 1, r) or
20            isPalindrome(l, r - 1)
21        )
23    l += 1
24    r -= 1
26return True

Objective

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

Key Insight

The two-pointer traversal efficiently detects the first mismatch. At that point, the algorithm branches to check two substrings formed by skipping either the left or right mismatched character. This conditional branching is the core mechanism that allows at most one deletion, ensuring correctness and linear time.

Interview Quick-Check

Core Logic

On mismatch, the algorithm checks if either skipping the left or right character yields a palindrome, which is the only valid deletion allowed.

State & Boundaries

The while loop condition l < r ensures pointers do not cross, covering all character pairs.

Common Pitfalls & Bugs

Not checking both substrings after mismatch or adding extra deletions leads to incorrect results.

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.

Line 17 Core

if s[l] != s[r]:

Check if the current characters at pointers l and r differ.

Detecting the first mismatch is the critical branching point where the algorithm must consider deleting one character.

Line 18 Core

return (

Begin returning the result of checking the two possible substrings formed by skipping one character.

If a mismatch occurs, the algorithm attempts to resolve it by deleting either the left or right character.

Line 19 Core

isPalindrome(l + 1, r) or

Call the helper function to verify if the substring excluding the left character is a palindrome.

Skipping the left character tests whether deleting s[l] fixes the palindrome structure.

Line 20 Core

isPalindrome(l, r - 1)

Call the helper function to verify if the substring excluding the right character is a palindrome.

Skipping the right character tests the alternative deletion possibility.

Line 21 Standard

Complete the return statement combining both deletion scenarios.

Combining both checks ensures that either possible deletion is evaluated.

Line 6 Standard

if s[l] != s[r]:

Check whether the characters at the current left and right pointers differ.

A single mismatch immediately proves the substring cannot be a palindrome.

Line 7 Standard

return False

Return False immediately if a mismatch is detected.

Early termination prevents unnecessary comparisons once the palindrome property is violated.

Line 8 Standard

l += 1

Advance the left pointer toward the center.

Moving the left pointer inward progresses the symmetric comparison.

Line 9 Standard

r -= 1

Move the right pointer toward the center.

Moving the right pointer inward continues checking mirrored characters.

Line 10 Standard

return True

Return True once all symmetric character checks pass.

If the loop completes without mismatches, the substring is confirmed to be a palindrome.

Line 12 Standard

l = 0

Initialize the left pointer at the start of the string.

Initializing the left pointer at the beginning enables inward palindrome verification.

Line 13 Standard

r = len(s) - 1

Initialize the right pointer at the end of the string.

Initializing the right pointer at the end complements the left pointer for symmetric traversal.

Line 15 Standard

while l < r:

Iterate inward while the left pointer remains before the right pointer.

The loop ensures every mirrored pair of characters is compared until the pointers meet.

Line 23 Standard

l += 1

Increment the left pointer after confirming characters match.

Advancing the pointer continues inward traversal when characters match.

Line 24 Standard

r -= 1

Decrement the right pointer after confirming characters match.

Symmetric pointer movement ensures mirrored pairs continue to be checked.

Line 26 Standard

return True

Return True when the string is already a palindrome or becomes one with at most one deletion.

If the entire traversal completes without requiring more than one deletion, the string satisfies the palindrome condition.

Test Your Understanding

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

Because the first mismatch is the only opportunity to delete a character. Skipping either the left or right character at this point tests both possible deletions. If neither substring is a palindrome, no single deletion can fix the string.

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`