Free Strings lessonsStrings · Stage 2 · Two pointers on text · Step 2

One mismatch allowed

Check whether deleting at most one character makes a palindrome. About 10 minutes.

Walk in until something differs

Your spell checker might say: "this is almost a palindrome, delete one letter and it is". Is "abca" one? Delete the b and you get "aca". Yes.

Start exactly as before, comparing from both ends and moving inwards while the characters match. If the fingers meet, it was already a palindrome and nothing needs deleting.

Same start as before: compare the two ends and move inwards.

s = "abca", one delete allowed

leftright

'a' and 'a' match. Step inward.

Move 1 of 4

At the first mismatch, try both

When two characters differ, one of them has to go, but which? You don't need to guess. Check whether the part between the fingers is a palindrome without the left character, and whether it is without the right one. If either works, the answer is yes.

You get only one delete, so those two checks are plain palindrome checks: no more skipping allowed.

Try dropping each side: either one working means yes.

One delete only: the two checks can't skip anything else.

In code

def is_pal(i, j):
    while i < j:
        if s[i] != s[j]:
            return False
        i, j = i + 1, j - 1
    return True
i, j = 0, len(s) - 1
while i < j:
    if s[i] != s[j]:
        return (is_pal(i + 1, j)
            or is_pal(i, j - 1))
    i, j = i + 1, j - 1
return True

Quick check

Walking "abccbxa" inward from both ends, which pair is the first mismatch?

Ab and x
Ba and c
CNone: it's a palindrome

Show the answer

b and x. a = a, then b (position 1) meets x (position 5): the first mismatch.

Your problem

Palindrome after one delete

You get a string. Return true if it reads the same forwards and backwards after deleting at most one character, and false otherwise.

Example

s = "abca" → true

0 ≤ length ≤ 100,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.