Coding Interview Patterns Module 4 – Two pointers

Two pointers on strings: palindromes and edits

Decide whether a code reads the same backwards after deleting at most one character: the problem, its examples and why trying every deletion is O(n²).

Intermediate
25 minutes
Examples run with Python 3.14.8 and Pyodide 314.0.7
By MySmartCoPilot

Free: The problem: does a code mirror after one deletion? · Trying every deletion makes the check quadratic. With a pass: the other 10 sections and 3 interview answers, about 20 minutes.

What you will learn

Check palindromes with at most one deletion in O(n) time
Prove that the linear check finds every answer one deletion allows
Compare strings typed with backspaces without building new strings
Handle case, normalisation and grapheme rules explicitly in comparisons
Decide whether two strings are exactly one edit apart with two pointers

Before you start

Two pointers: converging and reader–writer

What you’ll learn · Before you start

What you will learn

Check palindromes with at most one deletion in O(n) time
Prove that the linear check finds every answer one deletion allows
Compare strings typed with backspaces without building new strings
Handle case, normalisation and grapheme rules explicitly in comparisons
Decide whether two strings are exactly one edit apart with two pointers

Before you start

Two pointers: converging and reader–writer

On this page

A string is a palindrome: A string that reads the same forwards and backwards, such as level or kayak. Comparing characters from both ends towards the middle checks it in one pass. when it reads the same backwards, and two pointers check that by comparing characters from both ends towards the middle: about 100,000 comparisons for a code of 200,000 characters, O(n) time and O(1) extra memory, with no reversed copy. The same kind of scan handles small edits, such as deleting one character, comparing text typed with backspaces, or telling whether two strings are one edit apart.

The problem below allows one deletion. Trying every deletion costs about 2 × 10¹⁰ comparisons at that size, and the first mismatch gives the signal that leads to a linear answer.

The problem: does a code mirror after one deletion?

The problem

A shop prints product codes made of the lowercase letters a to z and the digits 0 to 9. A code nearly mirrors when deleting at most one character makes it read the same backwards. Write nearly_mirrors(code), which returns True or False. Limits: 1 ≤ n ≤ 200,000 characters. The codes are plain ASCII, so the rules of case and Unicode do not arise here; a field holding people’s names would need them.

"level" gives True: it mirrors already, so no deletion is needed.
"k2ayak" gives True: deleting the 2 leaves "kayak".
"zx9yz" gives False: no single deletion makes it mirror.

The second example is why the problem allows one deletion: kayak mirrors and k2ayak does not, so a single misprinted character is enough to break a code that should read the same both ways. The three examples, one row each:

The three examples of the problem

Text description of the diagram

The figure shows the three codes of the problem, one row of character cells each.

level: the cells l, e, v, e and l. It reads the same backwards already, so the answer is True.
k2ayak: the cells k, 2, a, y, a and k, with the 2 drawn dashed because it is deleted. What is left, kayak, reads the same backwards, so the answer is True.
zx9yz: the cells z, x, 9, y and z. No single deletion makes it read the same backwards, so the answer is False.

Checkpoint

Check: A code that mirrors after one deletion

One question Does the code rotator7 nearly mirror?
Choose one answer.

False: it does not read the same backwards True: it mirrors already False: two deletions are needed True: deleting the 7 leaves rotator, which reads the same backwards

Show the answer: One question

Answer: True: deleting the 7 leaves rotator, which reads the same backwards

rotator7 starts with r and ends with 7, so it does not mirror as it is. Deleting the 7 leaves rotator, which reads the same backwards, so the code nearly mirrors.

Trying every deletion makes the check quadratic

Check the code itself, then the code with each character deleted in turn: n + 1 palindrome checks of up to n/2 comparisons each. The method is plainly correct, and it costs O(n²). Step through it on the third example:

Interactive · line by line Trying every deletion of zx9yz Step through the brute force. It builds the code itself and each of its five deletions, then checks each one from both ends.

Program · trace/each_deletion_steps.py

code = "zx9yz"
tries = [code] + [code[:d] + code[d + 1 :] for d in range(len(code))]
answer = False
for text in tries:
    lo, hi = 0, len(text) - 1
    while lo < hi and text[lo] == text[hi]:
        lo += 1
        hi -= 1
    if lo >= hi:
        answer = True
        break
print(answer)

Variables

just taken by the loop
changed in this step
passed by the loop
read next
where the loop stopped

Printed so far

Nothing printed yetFalse

Every step was recorded from a run with Python 3.14.8 on macOS 26 arm64.

The drawing shows the variables when the program ends, and the program's 47 steps are listed below.

Line run 12

Next line end

Loop pass –

Every step as text

Start. No line has run yet, so there are no variables. Python starts with line 1.
Line 1. code = "zx9yz" sets code to 'zx9yz'.
Line 2. tries = [code] + [code[:d] + code[d + 1 :] for d in range(len(code))] runs.
Line 2. tries = [code] + [code[:d] + code[d + 1 :] for d in range(len(code))] runs.
Line 2. tries = [code] + [code[:d] + code[d + 1 :] for d in range(len(code))] runs.
Line 2. tries = [code] + [code[:d] + code[d + 1 :] for d in range(len(code))] runs.
Line 2. tries = [code] + [code[:d] + code[d + 1 :] for d in range(len(code))] runs.
Line 2. tries = [code] + [code[:d] + code[d + 1 :] for d in range(len(code))] sets tries to ['zx9yz', 'x9yz', 'z9yz', 'zxyz', 'zx9z', 'zx9y'].
Line 3. answer = False sets answer to False.
Line 4. for text in tries: takes the item at position 0 of tries: text is 'zx9yz'.
Line 5. lo, hi = 0, len(text) - 1 sets lo to 0 and sets hi to 4.
Line 6. while lo < hi and text[lo] == text[hi]: tests its condition: it is true (lo is 0, hi is 4 and text is 'zx9yz'), so the body runs.
Line 7. lo += 1 changes lo from 0 to 1.
Line 8. hi -= 1 changes hi from 4 to 3.
Line 6. while lo < hi and text[lo] == text[hi]: tests its condition: it is false (lo is 1, hi is 3 and text is 'zx9yz'), so the loop ends.
Line 9. lo >= hi is false (lo is 1 and hi is 3), so Python skips the block under if lo >= hi:. The code itself does not mirror. z matches z, but x and y differ, so the scan stops with lo below hi.
Line 4. for text in tries: takes the item at position 1 of tries: text is 'x9yz'.
Line 5. lo, hi = 0, len(text) - 1 sets lo to 0 (it was 1) and hi keeps its value, 3.
Line 6. while lo < hi and text[lo] == text[hi]: tests its condition: it is false from the start (lo is 0, hi is 3 and text is 'x9yz'), so the body never runs.
Line 9. lo >= hi is false (lo is 0 and hi is 3), so Python skips the block under if lo >= hi:.
Line 4. for text in tries: takes the item at position 2 of tries: text is 'z9yz'.
Line 5. lo, hi = 0, len(text) - 1 lo keeps its value, 0 and hi keeps its value, 3.
Line 6. while lo < hi and text[lo] == text[hi]: tests its condition: it is true (lo is 0, hi is 3 and text is 'z9yz'), so the body runs.
Line 7. lo += 1 changes lo from 0 to 1.
Line 8. hi -= 1 changes hi from 3 to 2.
Line 6. while lo < hi and text[lo] == text[hi]: tests its condition: it is false (lo is 1, hi is 2 and text is 'z9yz'), so the loop ends.
Line 9. lo >= hi is false (lo is 1 and hi is 2), so Python skips the block under if lo >= hi:.
Line 4. for text in tries: takes the item at position 3 of tries: text is 'zxyz'.
Line 5. lo, hi = 0, len(text) - 1 sets lo to 0 (it was 1) and sets hi to 3 (it was 2).
Line 6. while lo < hi and text[lo] == text[hi]: tests its condition: it is true (lo is 0, hi is 3 and text is 'zxyz'), so the body runs.
Line 7. lo += 1 changes lo from 0 to 1.
Line 8. hi -= 1 changes hi from 3 to 2.
Line 6. while lo < hi and text[lo] == text[hi]: tests its condition: it is false (lo is 1, hi is 2 and text is 'zxyz'), so the loop ends.
Line 9. lo >= hi is false (lo is 1 and hi is 2), so Python skips the block under if lo >= hi:.
Line 4. for text in tries: takes the item at position 4 of tries: text is 'zx9z'.
Line 5. lo, hi = 0, len(text) - 1 sets lo to 0 (it was 1) and sets hi to 3 (it was 2).
Line 6. while lo < hi and text[lo] == text[hi]: tests its condition: it is true (lo is 0, hi is 3 and text is 'zx9z'), so the body runs.
Line 7. lo += 1 changes lo from 0 to 1.
Line 8. hi -= 1 changes hi from 3 to 2.
Line 6. while lo < hi and text[lo] == text[hi]: tests its condition: it is false (lo is 1, hi is 2 and text is 'zx9z'), so the loop ends.
Line 9. lo >= hi is false (lo is 1 and hi is 2), so Python skips the block under if lo >= hi:.
Line 4. for text in tries: takes the item at position 5 of tries: text is 'zx9y'.
Line 5. lo, hi = 0, len(text) - 1 sets lo to 0 (it was 1) and sets hi to 3 (it was 2).
Line 6. while lo < hi and text[lo] == text[hi]: tests its condition: it is false from the start (lo is 0, hi is 3 and text is 'zx9y'), so the body never runs.
Line 9. lo >= hi is false (lo is 0 and hi is 3), so Python skips the block under if lo >= hi:.
Line 4. for text in tries: finds no item at position 6 of tries (it has 6 items), so the loop ends.
Line 12. print(answer) prints False. That was the last line, so the program ends. Six candidates were built and checked, n + 1 for n = 5, and none mirrors. On a code of 200,000 characters the same plan makes about 2 × 10¹⁰ comparisons.

Trying every deletion, with the comparisons counted Python · brute/each_deletion.py

"""The first answer: check the code, then the code without each character in turn. It counts the character
comparisons of the palindrome checks."""


def nearly_mirrors_slow(code):
    comparisons = 0

    def mirrors(text):
        nonlocal comparisons
        lo, hi = 0, len(text) - 1
        while lo < hi:
            comparisons += 1
            if text[lo] != text[hi]:
                return False
            lo += 1
            hi -= 1
        return True

    if mirrors(code):
        return True, comparisons
    for d in range(len(code)):
        if mirrors(code[:d] + code[d + 1:]):
            return True, comparisons
    return False, comparisons


for code in ["level", "k2ayak", "zx9yz"]:
    answer, comparisons = nearly_mirrors_slow(code)
    print(f"{code!r}: {answer}, {comparisons} comparisons")

print()
print("The worst case: one letter repeated, three different characters in the middle (no single deletion works)")
for n in [1_000, 2_000, 4_000]:
    half = (n - 3) // 2
    code = "a" * half + "bcd" + "a" * (n - 3 - half)
    answer, comparisons = nearly_mirrors_slow(code)
    print(f"n = {n:>5,}: {answer}, {comparisons:>10,} comparisons")
n = 200_000
print(f"n = {n:,}: about {n * n // 2:,} comparisons")

Output

'level': True, 2 comparisons
'k2ayak': True, 5 comparisons
'zx9yz': False, 10 comparisons

The worst case: one letter repeated, three different characters in the middle (no single deletion works)
n = 1,000: False,    499,001 comparisons
n = 2,000: False,  1,998,001 comparisons
n = 4,000: False,  7,996,001 comparisons
n = 200,000: about 20,000,000,000 comparisons

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 each_deletion.py

Reverse Text, Mirror & Upside Down Reverse a code of your own to see where it stops reading the same backwards.

The worst case is a code that needs two deletions, such as one letter repeated with three different characters in the middle: every check runs to the middle before it fails. The comparisons of this brute force: The simplest method that is plainly correct, usually trying every possibility. Said first in a round, it confirms what the problem asks, and later it checks a faster version's answers. More in “A six-step method for any coding problem” grow as n²/2, so at 200,000 characters they reach about 2 × 10¹⁰, where a single scan from both ends makes about 10⁵.

Checkpoint

Check: Trying every deletion, and what it costs

One question By the recorded counts, how many comparisons does the try-every-deletion brute force make on its worst code of 1,000 characters?
Type a number.
Your answer comparisons

A hint

Every one of the 1,001 checks runs to the middle before it fails.

Show the answer: One question

Answer: 499001 comparisons

Each of the 1,001 palindrome checks runs to the middle of the code before failing, about 500 comparisons each, so the total is about n²/2: 499,001 for n = 1,000 and four times as many for each doubling.

What to notice: the first mismatch decides

A palindrome check stops at the first pair that differs, and every pair outside that point has already matched. A single deletion can only help if it changes which characters face each other at that first mismatch, and that points at the two characters of the mismatched pair. The figure shows the first mismatch of the second example:

Comparing k2ayak from both ends, up to the first mismatch

Text description of the diagram

The diagram has two rows, one under the other.

The code k2ayak is drawn as six cells, each with a mark under its character. The first and last cells, k and k, are marked with an equals sign: they matched. The cells at positions 1 and 4, the digit 2 and the letter a, are marked with a not-equals sign: they differ. The two middle cells, a and y, are marked with a question mark: they were not compared yet.
The comparisons are listed in order: positions 0 and 5 hold k and k, which match; positions 1 and 4 hold 2 and a, which differ, and that is the first mismatch. A last line explains the three marks.

Checkpoint

Check: The first mismatch decides

One question Comparing k2ayak from both ends, which pair is the first mismatch?
Choose one answer.

Positions 0 and 5: k against k Positions 1 and 4: the 2 against an a Positions 2 and 3: a against y There is no mismatch

Show the answer: One question

Answer: Positions 1 and 4: the 2 against an a

The scan compares k with k, a match, then the 2 at position 1 with the a at position 4, which differ. That first mismatch is where a single deletion has to help, as the figure shows.

These questions start with your weakest idea.

Two tries at the first mismatch, step by step Pro: opens with a Pro, Premium or Ultimate pass

In this part:

A dry run on two codes
A proof that two tries are enough
The code in 14 languages
Two shortcuts that fail, found by trying every short code
Backspaces, compared from the right
Case, accents and Unicode, decided before you code
Up to k deletions: branching and a cache
Practise: one edit apart
- Tell whether two codes are exactly one edit apart
- A practice set with sample answers
Interview questions
- A candidate decides in O(n) whether a string becomes a palindrome after deleting at most one character, by trying only a few deletions. Which deletions must be tried, and why can no other deletion be the only fix? Prove it.
- Generalise the one-deletion palindrome check to at most k deletions, for strings of up to 10⁵ characters and k up to 100. How does the cost grow with k, what does caching change, and what would you use for the largest inputs?
- A product team wants a palindrome check for display names in any language, ignoring case and punctuation. Where does comparing code points after lower() go wrong, and what would you compare instead? Give concrete inputs.
Key takeaways

3 diagrams · 8 runnable examples (Python) · 1 exercise with sample tests · 3 interview answers · about 45 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Terms in this lesson

palindrome: A string that reads the same forwards and backwards, such as level or kayak. Comparing characters from both ends towards the middle checks it in one pass.

References

str.casefold() (The Python Standard Library: built-in types) (Python Software Foundation)
unicodedata.normalize() (The Python Standard Library) (Python Software Foundation)
unicodedata.iter_graphemes() (The Python Standard Library, Python 3.15) (Python Software Foundation)
Unicode Standard Annex #15: Unicode Normalization Forms (Unicode Consortium)
Unicode Standard Annex #29: Unicode Text Segmentation (Unicode Consortium)
Unicode Technical Standard #51: Unicode Emoji (flag sequences) (Unicode Consortium)
Intl.Segmenter (JavaScript reference) (MDN Web Docs)
String.charAt(int) (Java SE 25 API) (Oracle)
The Go Programming Language Specification: index expressions (The Go Authors)
str::as_bytes (The Rust Standard Library) (The Rust Project)
String.codeUnitAt (Dart API reference) (Dart (Google))
Strings and characters (The Swift Programming Language) (Swift.org)
str_split (PHP manual) (The PHP Group)
String: UTF-16 characters, Unicode code points and grapheme clusters (JavaScript reference) (MDN Web Docs)
Characters (Kotlin documentation) (JetBrains)
Introduction to character encoding in .NET (Microsoft)
Metrics/MethodLength (RuboCop documentation) (RuboCop)

Report a problem with this lesson

In this module: Two pointers

Two pointers: converging and reader–writer Free lesson, Pro answers: 25 minutes
In-place compaction with reader–writer pointers Free intro, Pro: 4 of 20 minutes free
Dutch national flag: three-way partitioning Free intro, Pro: 4 of 20 minutes free
Merge two sorted arrays in place Free intro, Pro: 5 of 20 minutes free
Two pointers on strings: palindromes and edits Free intro, Pro: 5 of 25 minutes free

Your country

Two pointers on strings: palindromes and edits

What you will learn

Before you start

What you will learn

Before you start

The problem: does a code mirror after one deletion?

Trying every deletion makes the check quadratic

What to notice: the first mismatch decides

Two tries at the first mismatch, step by step Pro: opens with a Pro, Premium or Ultimate pass

References

Related tools