Valid Palindrome II: One Deletion Allowed

This problem takes the palindrome check and adds one decision. It is a favourite because the brute force is obvious and slow, and the fast version depends on one precise observation about where a deletion can possibly help. Candidates who find that observation but try only one side of it fail on inputs the interviewer keeps ready.

The problem

Given a string of lowercase letters, return True if it is a palindrome already, or can become one by deleting at most one character. Otherwise return False.

• "radkar" → True. Delete k to get "radar".
• "abccdba" → True. Delete d to get "abccba".
• "abcdef" → False. No single deletion helps.

Constraints: 1 ≤ len(text) ≤ 10⁵; lowercase English letters only.

Clarifying questions

• Is "zero deletions" allowed? Yes — a string that is already a palindrome returns True.
• Do we skip punctuation or ignore case? No; the input is lowercase letters only.
• Do we need to return which character to delete? No, just True or False. (It is an easy extension.)

Approach 1: the simple way

Check the string as it is; then try deleting each position in turn and check what remains.

1def almost_palindrome_brute(text: str) -> bool:2    """Try the string as it is, then every single deletion."""3    if text == text[::-1]:4        return True5    for i in range(len(text)):6        candidate = text[:i] + text[i + 1:]7        if candidate == candidate[::-1]:8            return True9    return False

Time O(n²), space O(n). There are n deletions, and each builds a new string and reverses it in O(n). At n = 10⁵ that is about 10¹⁰ character operations — far over budget. Worse, almost all of those deletions are pointless, as the next section shows.

The key insight

Walk two pointers inward as in a normal palindrome check. While the characters match, nothing needs deleting — those pairs are already mirrored. Stop at the first mismatch, at positions left and right.

Now ask which deletions could possibly help.

• A character strictly between left and right. Everything shifts by one on one side only, but text[left] and text[right] still end up as a mirror pair — still unequal. Useless.
• A character before left (or after right). This can work, but only in one situation: when the characters from that position up to left are all the same letter. Deleting any letter from a run of equal letters produces the same string, so it is the same as deleting text[left] itself. (We checked this on every string of up to 9 letters from a, b, c: all 1,008 working "outside" deletions fell inside such a run.)

So only two options really remain:

• Delete text[left]: check whether text[left + 1 .. right] is a palindrome.
• Delete text[right]: check whether text[left .. right - 1] is a palindrome.

If either is, the answer is True. If neither is, no single deletion can work. The whole search collapses from n candidates to two, and each check is a plain linear scan with no further deletions allowed — the one deletion has been spent.

Take "abccdba". The outer pairs a…a and b…b match, so they are already mirrored and nothing there needs deleting. The first mismatch is c (position 2) against d (position 4). Deleting the a at the front cannot help — the new string "bccdba" starts with b and ends with a. Deleting the b at position 5 cannot help either — "abccda" now pairs b with d. Only c or d are worth trying.

Approach 2: two pointers with one fork

1def is_range_palindrome(text: str, left: int, right: int) -> bool:2    """True if text[left..right] (inclusive) is a palindrome."""3    while left < right:4        if text[left] != text[right]:5            return False6        left += 17        right -= 18    return True91011def almost_palindrome(text: str) -> bool:12    """True if text is a palindrome after deleting at most one character."""13    left, right = 0, len(text) - 114    while left < right:15        if text[left] != text[right]:16            return (is_range_palindrome(text, left + 1, right)     # drop the left one17                    or is_range_palindrome(text, left, right - 1))  # drop the right one18        left += 119        right -= 120    return True                          # no mismatch: already a palindrome

The helper takes index bounds instead of slices, so no new strings are built. A shorter version is tempting: at the mismatch, return a == a[::-1] or b == b[::-1] for the two slices a and b. It is still O(n) time and it is fine to say out loud, but each slice and each reversal copies up to n characters, so it uses O(n) space. If the interviewer asked for constant space, the index-based helper is the answer.

Notice also that the main loop returns at the first mismatch. It never continues past it. Everything outside [left, right] has already matched, and everything inside is handled by the helper, so there is nothing left for the main loop to do.

Dry run on "abccdba" (positions a0 b1 c2 c3 d4 b5 a6):

Deleting the d at position 4 gives "abccba", which is exactly what branch 3b checked.

Complexity. The main loop and the two helper calls each move pointers inward over disjoint or shrinking ranges; in total no more than about 2n character comparisons. O(n) time, O(1) space.

Edge cases

• One character, such as "a". The loop never runs → True.
• Two different characters, such as "ab". Mismatch at once; dropping either leaves one character, a palindrome → True.
• "abc". Mismatch a vs c; "bc" and "ab" both fail → False.
• The left branch fails but the right one works, as in "abccdba" or the short "aab". This is the case that catches one-sided code.
• Both branches work, as in "radkar": the first mismatch is d against k, and deleting either gives a palindrome ("rakar" or "radar"). The or returns on the first.

This problem is easy to get subtly wrong, so it is a good one to test against the brute force. We compared the two on 2,000 random strings of up to 9 letters drawn from a, b and c — a small alphabet makes near-palindromes common — and they agreed on every one. A random search over the same alphabet also finds one-sided bugs at once: "aab" is among the first failures it reports.

Follow-ups

• "Allow up to k deletions." Fork again at each mismatch with k − 1 left. Without memoisation that is up to 2^k branches; memoising on (left, right, k) bounds it, and for large k this becomes the dynamic-programming problem "minimum deletions to make a palindrome", O(n²).
• "Return the index to delete." Return left or right from whichever branch succeeds, or -1 if the string is already a palindrome.
• "Ignore punctuation and case too." Combine this with the skip loops from Valid Palindrome, applied inside both the main loop and the helper.