Valid Palindrome II

Valid Palindrome II is a clean two-pointer question. It tests something simple. Can you check a string from both ends and handle one mismatch in a smart way? The interviewer wants to see if you can split into two small checks instead of trying every deletion.

🎯 The Problem

You get a string and one allowed deletion. Decide if the string can become a palindrome. The rules:

• A palindrome reads the same forward and backward, like racecar or aba.
• You may delete at most one character.
• Return true if some single deletion makes it a palindrome.
• An already-palindrome string is also true, since deleting nothing is allowed.
• If no single deletion can fix it, return false.

For the string abca, deleting the c gives aba, which reads the same both ways. So the answer is true. One deletion was enough.

Input:  s = "abca"
Output: true

Explanation: delete 'c' to get "aba", which is a palindrome.

Here is the idea. Two pointers start at the ends and walk inward, comparing letters.

🐢 Approach 1: Try Every Deletion (Brute Force)

Delete one character at a time and test the result.

The idea:

• Delete the first character and check if the rest is a palindrome.
• Then delete the second, and so on for every position.
• Also check the original with no deletion.

Why it is weak:

• For each deletion you build a new string and check the whole thing.
• That check is O(n), done for every one of the n positions.
• Total time is O(n²). Correct but slow.

Here is the brute-force code for that idea:

def valid_palindrome(s):
    if s == s[::-1]:
        return True

    for i in range(len(s)):
        candidate = s[:i] + s[i + 1:]
        if candidate == candidate[::-1]:
            return True

    return False

⚡ Approach 2: Two Pointers With One Skip (Best)

The idea in one line: walk in from both ends, and at the first mismatch spend your single deletion on the left letter or the right letter.

The idea:

• Put one pointer at the start and one at the end.
• Walk them inward and compare the two letters each step.
• While letters match, keep moving both in.

How it works:

• The trouble starts only at the first mismatch.
• That is where you spend the one allowed deletion.
• Try skipping the left letter: check if the range from left plus one to right is a palindrome.
• Try skipping the right letter: check if the range from left to right minus one is a palindrome.
• If either range is a palindrome, the answer is true. If neither works, false.

Why it is fast:

• The palindrome check is just another two-pointer walk with no skips.
• The extra check runs only once, at the first mismatch.
• Total time is O(n) and space is O(1).

Here is the dry-run for abca.

Steps to Solve

1. Put a left pointer at the start and a right pointer at the end.
2. While left is before right, compare the two letters.
3. If they match, move both pointers inward and continue.
4. If they do not match, check two things: skip the left letter, or skip the right letter.
5. Each check is a plain palindrome test on the smaller range.
6. Return true if either check passes. If the loop finishes with no mismatch, return true.

#include <stdio.h>
#include <string.h>

int isRange(const char *s, int left, int right) {
    while (left < right) {
        if (s[left] != s[right]) return 0;   // mismatch, not a palindrome
        left++;
        right--;
    }
    return 1;
}

int validPalindrome(const char *s) {
    int left = 0;
    int right = (int)strlen(s) - 1;
    while (left < right) {
        if (s[left] != s[right]) {
            // try skipping left OR skipping right
            return isRange(s, left + 1, right) || isRange(s, left, right - 1);
        }
        left++;
        right--;
    }
    return 1;   // already a palindrome
}

int main(void) {
    const char *s = "abca";
    printf("%s\n", validPalindrome(s) ? "true" : "false");
    return 0;
}

true

#include <iostream>
#include <string>
using namespace std;

bool isRange(const string& s, int left, int right) {
    while (left < right) {
        if (s[left] != s[right]) return false;   // mismatch
        left++;
        right--;
    }
    return true;
}

bool validPalindrome(const string& s) {
    int left = 0, right = (int)s.size() - 1;
    while (left < right) {
        if (s[left] != s[right]) {
            // try skipping left OR skipping right
            return isRange(s, left + 1, right) || isRange(s, left, right - 1);
        }
        left++;
        right--;
    }
    return true;   // already a palindrome
}

int main() {
    string s = "abca";
    cout << (validPalindrome(s) ? "true" : "false") << endl;
    return 0;
}

true

public class ValidPalindromeII {
    static boolean isRange(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;  // mismatch
            left++;
            right--;
        }
        return true;
    }

    public static boolean validPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                // try skipping left OR skipping right
                return isRange(s, left + 1, right) || isRange(s, left, right - 1);
            }
            left++;
            right--;
        }
        return true;   // already a palindrome
    }

    public static void main(String[] args) {
        String s = "abca";
        System.out.println(validPalindrome(s) ? "true" : "false");
    }
}

true

def valid_palindrome(s):
    def is_range(left, right):
        while left < right:
            if s[left] != s[right]:    # mismatch in this range
                return False
            left += 1
            right -= 1
        return True

    left = 0
    right = len(s) - 1
    while left < right:
        if s[left] != s[right]:
            # spend the one deletion: skip left OR skip right
            return is_range(left + 1, right) or is_range(left, right - 1)
        left += 1
        right -= 1
    return True                        # already a palindrome


s = "abca"
print("true" if valid_palindrome(s) else "false")

true

function validPalindrome(s) {
  function isRange(left, right) {
    while (left < right) {
      if (s[left] !== s[right]) return false; // mismatch
      left++;
      right--;
    }
    return true;
  }

  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    if (s[left] !== s[right]) {
      // spend the one deletion: skip left OR skip right
      return isRange(left + 1, right) || isRange(left, right - 1);
    }
    left++;
    right--;
  }
  return true; // already a palindrome
}

const s = "abca";
console.log(validPalindrome(s) ? "true" : "false");

true

Let us walk through the Python version line by line. The clever part is what happens at the mismatch.

def is_range(left, right): is a small helper. It checks if the part of the string between two positions reads the same both ways. It is a plain two-pointer palindrome test with no deletions. We reuse it for both skip choices.

left = 0 and right = len(s) - 1 set the main pointers at the two ends of the string.

while left < right: walks the pointers inward.

if s[left] != s[right]: catches the first mismatch. This is the only place we ever spend the deletion. We return is_range(left + 1, right) or is_range(left, right - 1). The first call skips the left letter. The second call skips the right letter. If either smaller range is a palindrome, the whole answer is true. The or returns true if at least one passes.

left += 1 and right -= 1 move both pointers in when the letters match. If the loop finishes without ever hitting a mismatch, the string was already a palindrome. So we return True. We never needed the deletion at all.

⏱️ Time and Space Complexity

The brute force tries every deletion and checks the whole string each time, so it is O(n²) time. The two-pointer way walks the string once, and at the single mismatch it does one extra range check. That extra check is O(n) but it happens only once. So the whole thing is O(n) time and O(1) space.

🧩 Key Takeaways

• ✅ Walk two pointers inward and compare letters from both ends.
• ✅ The first mismatch is the only place you spend the one deletion.
• ✅ At the mismatch, try skipping the left letter or the right letter.
• ✅ Each skip turns into a plain palindrome check on a smaller range.
• ✅ The two-pointer method runs in O(n) time with O(1) extra memory.

🚀 What’s Next?

• Trapping Rain Water
• Two Sum II - Input Array Is Sorted