Valid Palindrome II: Delete One Character, Two Pointers

You're given a string s of lower-case letters. Return true if it's a palindrome already or can be made into one by deleting at most one of its characters, and false if it can't.

Examples

Input	Output	Why
`s = "abca"`	`true`	Delete the b or the c.
`s = "aba"`	`true`	It's a palindrome as it stands.
`s = "abc"`	`false`
`s = "cbbcc"`	`true`	Deleting one of the two c's at the end gives cbbc. Deleting the first c or a b does not work.

Constraints

1 ≤ s.length ≤ 10⁵
s has lower-case English letters only

Hints

Hint 1

Trying every deletion and checking each result costs O(n²). Where's the first place a deletion could matter?

Hint 2

Walk two pointers in from the ends while the letters match. Those pairs are fine whatever you delete further in.

Hint 3

At the first mismatch one of s[lo] and s[hi] has to go. So you check whether s[lo+1..hi] or s[lo..hi−1] is a palindrome, and you don't get a second deletion.

Where people lose marks

Trying only one side at the mismatch. You'll pass most tests and then fail on something like cbbcc where it's the other letter that has to go.
Letting the inner check skip again. That allows two deletions and you'll say true for strings like abcdeca.
Building new substrings for each check. It's still O(n) but it copies, and in an interview I'd pass the two indices instead.

Dry run on `"cbbcc"`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 6

Step 1 / 6

s
c0lob1b2c3c4hi
lo0hi4
lo and hi start at the two ends and walk in while the letters match.
Step 2 / 6

s
c0lob1b2c3c4hi
lo0hi4
s[0] = s[4] = c. This pair is fine, move both in.
Step 3 / 6

s
c0b1lob2c3hic4
lo1hi3
s[1] = b but s[3] = c. One of them has to go, so try both.
Step 4 / 6

s
c0b1b2c3c4
drop lofalse
Drop s[1]: is bc a palindrome? No.
Step 5 / 6

s
c0b1b2c3c4
drop hitrue
Drop s[3]: is bb a palindrome? Yes.
Step 6 / 6

s
c0b1b2c3c4
resulttrue
One deletion is enough, so the answer is true.

How to think about it

If you try every possible deletion and check each string you've got O(n²), which is too slow at 10⁵. With two pointers walking in from the ends you only need to think about the first place the letters don't match.

Everything before that matched in pairs, and none of those pairs needs touching. At the first mismatch s[lo] ≠ s[hi] one of those two letters can't be in the final palindrome, and you don't know which, so you try both. Either s[lo+1..hi] is a palindrome or s[lo..hi−1] is, and if neither one is then a single deletion can't fix it. Each check is a plain scan with no more skips allowed, so it's two scans at most and O(n) in all.

I'd make sure to try both sides. In "cbbcc" the two outer c's match and then the b at index 1 meets the c at index 3, and it's only dropping the c on the right that works.

Complexity. Time O(n) · Space O(1)

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

def valid_palindrome(s):
    def pal(i, j):                      # no more deletions allowed in here
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

    lo, hi = 0, len(s) - 1
    while lo < hi:
        if s[lo] != s[hi]:              # one of the two has to go: try both
            return pal(lo + 1, hi) or pal(lo, hi - 1)
        lo += 1
        hi -= 1
    return True

#include <string>

static bool pal(const std::string& s, int i, int j) {   // no more deletions allowed in here
    for (; i < j; ++i, --j) if (s[i] != s[j]) return false;
    return true;
}

bool solve(const std::string& s) {
    for (int lo = 0, hi = (int)s.size() - 1; lo < hi; ++lo, --hi)
        if (s[lo] != s[hi]) return pal(s, lo + 1, hi) || pal(s, lo, hi - 1);   // one of the two has to go
    return true;
}

class Solution {
    private boolean pal(String s, int i, int j) {   // no more deletions allowed in here
        for (; i < j; i++, j--) if (s.charAt(i) != s.charAt(j)) return false;
        return true;
    }

    public boolean validPalindrome(String s) {
        for (int lo = 0, hi = s.length() - 1; lo < hi; lo++, hi--)
            if (s.charAt(lo) != s.charAt(hi)) return pal(s, lo + 1, hi) || pal(s, lo, hi - 1);   // one of the two has to go
        return true;
    }
}

function validPalindrome(s) {
  const pal = (i, j) => {             // no more deletions allowed in here
    for (; i < j; i++, j--) if (s[i] !== s[j]) return false;
    return true;
  };
  for (let lo = 0, hi = s.length - 1; lo < hi; lo++, hi--)
    if (s[lo] !== s[hi]) return pal(lo + 1, hi) || pal(lo, hi - 1);   // one of the two has to go
  return true;
}

fn pal(b: &[u8], mut i: usize, mut j: usize) -> bool {   // no more deletions allowed in here
    while i < j {
        if b[i] != b[j] { return false; }
        i += 1; j -= 1;
    }
    true
}

fn solve(s: &str) -> bool {
    let b = s.as_bytes();
    if b.len() < 2 { return true; }
    let (mut lo, mut hi) = (0usize, b.len() - 1);
    while lo < hi {
        if b[lo] != b[hi] { return pal(b, lo + 1, hi) || pal(b, lo, hi - 1); }   // one of the two has to go
        lo += 1; hi -= 1;
    }
    true
}

import Data.Array

solve :: String -> Bool
solve s = go 0 (n - 1)
  where
    n = length s
    a = listArray (0, max 0 (n - 1)) s
    -- no more deletions allowed in here
    pal i j
      | i >= j           = True
      | a ! i /= a ! j   = False
      | otherwise        = pal (i + 1) (j - 1)
    go lo hi
      | lo >= hi         = True
      | a ! lo /= a ! hi = pal (lo + 1) hi || pal lo (hi - 1)   -- one of the two has to go
      | otherwise        = go (lo + 1) (hi - 1)

Variants to try

If you're allowed k deletions the greedy idea stops working and it becomes the longest palindromic subsequence: you need n − LPS ≤ k, which is an O(n²) DP.
If you're asked which index to delete you return lo or hi from whichever of the two checks passed.

Next problems

Easy10 min

A palindrome after deleting at most one letter

Examples

Constraints

Hints

Where people lose marks

Dry run on `"cbbcc"`

How to think about it

The solution, in six languages

Variants to try

Next problems

Pair with a given sum in a sorted array

Count the pairs whose sum is below a target

A palindrome, ignoring punctuation and case

Keep going

Pair with a given sum in a sorted array

Count the pairs whose sum is below a target

A palindrome, ignoring punctuation and case

The pattern behind it

A palindrome after deleting at most one letter

Examples

Constraints

Hints

Where people lose marks

Dry run on "cbbcc"

How to think about it

The solution, in six languages

Variants to try

Next problems

Pair with a given sum in a sorted array

Count the pairs whose sum is below a target

A palindrome, ignoring punctuation and case

Keep going

Pair with a given sum in a sorted array

Count the pairs whose sum is below a target

A palindrome, ignoring punctuation and case

The pattern behind it

Dry run on `"cbbcc"`