DSA sheet · Strings · Two Pointers pattern

Valid Palindrome II

This is the next two-pointer string question after Valid Palindrome. The teacher warns that it looks easy but isn't: one extra line, "you may delete at most one character", changes the problem. The video shows the O(n²) brute force (try deleting every character), explains why the constraints reject it, and then builds an O(n) solution: walk two pointers inwards, and at the first mismatch try exactly two options, skip the left character or skip the right one. She also clears up a common confusion: this is not dynamic programming. It's asked in interviews, so the reasoning matters more than the few lines of code.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Two pointers from scratch (what you must know first)
• Part A · Brute force: try deleting every character
• Part B · Optimal: two pointers + two tries at the first mismatch
• Part C · Why trying both skips is enough (the proof)
• Part D · Revision page

Part 0 · Before starting: two pointers from scratch

Pointers are just indexes

A pointer here is an index into the string: "I'm looking at position i". Two pointers means we keep two indexes and move them by rules, instead of running two nested loops.

The brute force two pointers usually replaces

Trying every pair (i, j) with two loops costs O(n²). With n = 10⁵ that's about 10¹⁰ steps, way past the rough 10⁸ operations safe limit → TLE. Two pointers helps when the input lets us skip most pairs. In a sorted array, a sum that's too big tells us to move the right pointer left. In a palindrome, index i only ever needs its mirror index n − 1 − i, so the other pairs never need checking.

The two-pointer family (you'll meet all of these in the notebook)

Why two pointers and not sliding window (the teacher's rule)

Strings have two main patterns. Sliding window is for when we need everything in a continuous block between two ends. Two pointers is for when we compare exactly two points, then move them and compare the next two. A palindrome check compares the front character with the back one, nothing in between, so it's two pointers.

The basic palindrome check (from Valid Palindrome)

left = 0, right = n − 1. While left < right: if s[left] != s[right] → not a palindrome. Otherwise move both inwards. If the loop ends, it's a palindrome. We stop at left < right because when both point at the same middle character, it trivially equals itself. We'll reuse this check, but on a part of the string given by two indexes.

Words

• Palindrome: reads the same forwards and backwards ("aba", "aca").
• Delete at most one: you may delete zero characters or one character, never two.
• Window [l, r]: the part of the string from index l to index r, both included.

Part A · Brute force: try deleting every character

LeetCode 680

1The question in simple words

Given a string s (only lowercase letters), return True if you can make it a palindrome by deleting at most one character. Otherwise return False.

2What the constraints tell us

• 1 ≤ s.length ≤ 10⁵. The teacher's usual rule: past about 10⁸ operations it's risky, past 10⁹ it's certain TLE.
• An O(n²) idea → (10⁵)² = 10¹⁰ → TLE. So we already know the brute force won't be accepted and we must find something around O(n).
• Only lowercase English letters → no case or symbol handling (unlike Valid Palindrome I).

3Intuition

"At most one" means two things to check, in order:

1. Zero deletions: is s already a palindrome? If yes → True.
2. One deletion: delete each character one at a time, and test whether what's left is a palindrome. If any works → True.

For the palindrome test, the brute force uses the plain definition: reverse the string into a copy s1 and compare position by position.

4Building the logic from the example

Take s = "abca".

• No deletion: s = abca, s1 = reverse = acba. Position 1: b vs c → differ → not a palindrome. Go to deletions.
• Delete index 0 (a): s = bca, s1 = acb. b vs a → differ ✗.
• Delete index 1 (b): s = aca, s1 = aca. a = a, c = c, a = a → palindrome → return True.

The test itself is a small function: given s and its reverse s1 (same length n), loop i from 0 to n − 1. If s[i] != s1[i] → return False. After the loop → return True.

5Approach steps

1. If s equals its reverse → return True (zero deletions).
2. For each index i from 0 to n − 1: build t = s without index i.
3. If t equals its reverse (checked char by char) → return True.
4. If no deletion worked → return False.

6Code (Python)

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def same(a, b):                      # a and b have equal length
            for i in range(len(a)):
                if a[i] != b[i]:
                    return False
            return True

        if same(s, s[::-1]):                 # zero deletions
            return True
        for i in range(len(s)):              # try deleting each index
            t = s[:i] + s[i + 1:]
            if same(t, t[::-1]):
                return True
        return False

7Code line by line

8Dry run (hand table)

s = "abcda" (the False example):

All failed → False. We did 6 full checks on a 5-letter string. That's the n × n growth.

9Complexity & remember

• Time O(n²): up to n deletions, each followed by an O(n) copy + reverse + compare. n = 10⁵ → 10¹⁰ → TLE.
• Space O(n): the copies t and its reverse.

Part B · Optimal: two pointers + two tries at the first mismatch

1The question again, with the new goal

Same question. Goal: O(n) time, no copies of the string (O(1) extra space).

2What the constraints push us towards

n up to 10⁵ means O(n) or O(n log n). The brute force repeats almost the same palindrome check n times. The idea is to do the check once, and only "branch" at the one place where things go wrong.

3Intuition: walk until something breaks

Run the normal two-pointer palindrome check from both ends. As long as the characters match, nothing needs deleting, so keep walking inwards. At the first mismatch, s[left] != s[right], we know one of these two characters is the troublemaker. We're allowed to throw away just one of them, so try both:

• Skip the left one: is the window [left + 1, right] a palindrome?
• Skip the right one: is the window [left, right − 1] a palindrome?

If either is a palindrome → True. If neither → False. And if we never hit a mismatch, the string was already a palindrome (zero deletions) → True.

4Building the conditions from examples

Example 1: "abca"

Skip b → the window is just "c", a single character, so it's a palindrome → True (the whole string becomes "aca"). Skip c → window "b" would also be True. Either way the answer is True.

Example 2 (the teacher's second example): "afgfea"

• Skip f (left): window "gfe": g vs e ✗ → False.
• Skip e (right): window "fgf": f = f, then both pointers on g → True.

One of them is True, so the answer is True. Combine the two tries with or, because we need at least one to work, not both.

Condition: inside a try, no more deletions

When we test the window after skipping one character, we've already used our one deletion. So inside that check, the first mismatch means False immediately. Don't try to skip again; that would be a second deletion.

Condition: don't copy the string, pass indexes

The brute force built new strings. Here the helper takes the original s plus two indexes l and r, and checks only that window in place. Passing the whole s is fine, since the helper only ever looks between l and r. No s1, no extra space.

Condition: while left < right (in both loops)

Same as Valid Palindrome: when left = right both are on one character, which matches itself, so there's nothing to check.

Condition: on a mismatch, return the result of the tries

In the main loop, a mismatch does not mean False right away, because we still have one deletion. Instead we return whatever the two tries give. The main loop never continues after that point.

5Approach steps

1. Write a helper check(s, l, r): while l < r, if s[l] != s[r] → False, else move both inwards. After the loop → True.
2. Main: left = 0, right = len(s) − 1.
3. While left < right:
4.   if s[left] != s[right] → return check(s, left + 1, right) or check(s, left, right − 1);
5.   else → left += 1, right -= 1.
6. After the loop (no mismatch at all) → return True.

6Code (Python)

class Solution:
    def validPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        while left < right:
            if s[left] != s[right]:
                # one deletion allowed: skip the left char OR skip the right char
                return (self.isPalindromeRange(s, left + 1, right) or
                        self.isPalindromeRange(s, left, right - 1))
            left += 1
            right -= 1
        return True                          # no mismatch: zero deletions needed

    def isPalindromeRange(self, s, l, r):
        while l < r:
            if s[l] != s[r]:
                return False                 # deletion already used, so fail
            l += 1
            r -= 1
        return True

7Code line by line

8Dry run

s = "afgfea" (indexes 0–5)

s = "abcda" (the False case)

Compare with Part A: there we needed 6 full checks for this string. Here we made 2 main comparisons and 2 short tries.

s = "aba" (zero deletions)

a = a → move both → left = right = 1 → loop ends → True. The helper is never called.

9Complexity & remember

• Time O(n). The teacher counts it precisely: the main loop does about n/2 comparisons. At a mismatch, each helper call checks what's left, at most about n/2 each, and there are two calls. Total about n/2 + n/2 + n/2 = 3n/2, which is linear. Her interview tip: say "O(n)", but showing you can count it as 3n/2 shows clear thinking.
• Space O(1): only indexes, no copies. (If you wrote the tries with slicing like s[l+1:r+1] == s[l+1:r+1][::-1], time would still be O(n) but space would become O(n).)
• Much better than the O(n²) brute force. It passes easily for n = 10⁵.

Part C · Why trying both skips is enough

The code tries only 2 deletions instead of n. Why can't the right deletion be somewhere else? Here's the reasoning in three small steps.

1Where we are at the first mismatch

  s = [ x x x | s[l] . . . . . s[r] | x x x ]
        ^^^^^                         ^^^^^
        outer left part   ==   outer right part (mirrored), already matched
                       window [l, r], and s[l] != s[r]

Everything outside the window matched in mirror pairs. Inside, the two ends differ.

2We must delete exactly one character

s itself isn't a palindrome (s[l] ≠ s[r] are a mirror pair), so zero deletions won't work. Exactly one deletion is needed.

3Deleting something strictly inside the window can't work

Say we delete a character between l and r (not l, not r). The outer parts are untouched and still match, so in the new string the mirror pairs line up the same way, and s[l] and s[r] are still a mirror pair. They're still different, so it's not a palindrome. So the deleted character must be s[l] or s[r] itself. Those are exactly our two tries.

4What about deleting from the outer matched part?

Could it help to delete a character left of l (or right of r)? Then everything shifts by one, so it's less obvious. But here's the trick: if deleting an outer character at k < l gives a palindrome, the mirror matches force s[k] = s[k+1] = … = s[l] (each shifted character must equal its neighbour). In other words, k sits in a run of equal letters that reaches all the way to l. And deleting any one letter from a run of equal letters gives the same string. So deleting k gives exactly the same result as deleting l, which is our try 1. The right side works the same way and matches try 2.

5Why the greedy "match → move on" is safe

Steps 3 and 4 also show that while pairs keep matching, we never need to delete one of them. Any useful deletion out there is equivalent to deleting at the first mismatch. So walking inwards without branching on matches loses nothing. That's the "slightly greedy" part the teacher mentions.

6Why we fully check both, not just one

Both ends are candidates, and a one-step peek can't tell which is right (the "abbab" example in Part B). Checking both fully costs only about 2 × n/2, so it's still O(n).

The test file also checks this by comparing against the brute force on every string of a, b, c up to length 8.

Part D · Revision page

s = Solution()
print(s.validPalindrome("aba"))      # True  (zero deletions)
print(s.validPalindrome("abca"))     # True  (delete b or c)
print(s.validPalindrome("abc"))      # False
print(s.validPalindrome("abcda"))    # False
print(s.validPalindrome("afgfea"))   # True  (delete e)
print(s.validPalindrome("abbab"))    # True  (delete the last b)
print(s.validPalindrome("a"))        # True
print(s.validPalindrome("ab"))       # True  (delete either)

Based on this video: Valid Palindrome II | Two Pointers