Course4all
Join us on telegram
Home/dsa/Two Pointers/Valid Palindrome II

Valid Palindrome II

Master this topic with zero to advance depth.

Valid Palindrome II

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

String: "abca", l=0, r=3 1. s[0]=='a', s[3]=='a' -> Match. l=1, r=2. 2. s[1]=='b', s[2]=='c' -> Mismatch! 3. Option A: Delete 'b' (l=1). Check s[2..2] ("c"). Palindrome! 4. Option B: Delete 'c' (r=2). Check s[1..1] ("b"). Palindrome! Result: true
Easy

Examples

Input: s = "abca"
Output: true

You could delete the character 'c' to get 'aba', which is a palindrome.

Approach 1

Level I: Brute Force (Check All Deletions)

Intuition

For each character in the string, try deleting it and check if the resulting string is a palindrome. This covers all possible single-character deletions.

⏱ O(N^2)💾 O(N)

Detailed Dry Run

Input: "abca"

  1. Delete 'a': "bca" (No)
  2. Delete 'b': "aca" (YES!) Return true.
java
public boolean validPalindrome(String s) {
    for (int i = 0; i < s.length(); i++) {
        String t = s.substring(0, i) + s.substring(i + 1);
        if (isPalindrome(t)) return true;
    }
    return isPalindrome(s);
}
private boolean isPalindrome(String s) {
    int l = 0, r = s.length() - 1;
    while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
    return true;
}

⚠️ Common Pitfalls & Tips

O(N^2) complexity will TLE for large strings (N=10^5).

Approach 2

Level II: Better (Greedy with One Skip)

Intuition

Use two pointers from both ends. When characters don't match, we have two choices: delete the character at L or the character at R. If either resulting substring is a palindrome, the whole string satisfies the condition.

Iterate with L=0, R=n-1. If s[L] == s[R], move both. If not, check isPalindrome(s, L+1, R) OR isPalindrome(s, L, R-1).

⏱ O(N)💾 O(1)

Detailed Dry Run

Input: "abca"

  1. L=0(a), R=3(a). Match. L=1, R=2.
  2. L=1(b), R=2(c). Mismatch!
  3. Check isPalindrome("c", 2, 2) (YES) or isPalindrome("b", 1, 1) (YES). Return true.
java
public boolean validPalindrome(String s) {
    int l = 0, r = s.length() - 1;
    while (l < r) {
        if (s.charAt(l) != s.charAt(r)) {
            return isPalindrome(s, l + 1, r) || isPalindrome(s, l, r - 1);
        }
        l++; r--;
    }
    return true;
}
private boolean isPalindrome(String s, int l, int r) {
    while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
    return true;
}

⚠️ Common Pitfalls & Tips

Be careful with off-by-one errors when slicing substrings.

Approach 3

Level III: Optimal (Two Pointers - Greedy)

Intuition

Use two pointers starting from ends. If characters mismatch, we have two choices: delete the character at L or the character at R. If either resulting substring is a palindrome, the whole string satisfies the condition.

⏱ O(N)💾 O(1)

Detailed Dry Run

Input: s = "aba"

  • l=0, r=2: mismatch at s[1] vs s[2]? No, match. Input: s = "abca"
  • l=1 ('b'), r=2 ('c'): mismatch!
  • Check s[2..2] ("c"): Palindrome.
  • Check s[1..1] ("b"): Palindrome.
  • Return true.
java
class Solution {
    public boolean validPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                return isPalindrome(s, l + 1, r) || isPalindrome(s, l, r - 1);
            }
            l++; r--;
        }
        return true;
    }

    private boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--)) return false;
        }
        return true;
    }
}

⚠️ Common Pitfalls & Tips

After removing one character, the remaining string must be a perfect palindrome. Don't forget that l+1 and r-1 are the only two options.

← Previous QuestionSort Colors
Next Question →Minimum Size Subarray Sum