Valid Palindrome II

Easy
46.

Valid Palindrome II

Valid Palindrome II is an easy coding problem on strings, greedy and two pointers.

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

Example 1

Input
s = "aba"
Output
true

Example 2

Input
s = "abca"
Output
true
Explanation
Delete the "c".

Example 3

Input
s = "abc"
Output
false

Constraints

  • 1 <= s.length <= 40
  • Lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {boolean}
 */
var validPalindrome = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Valid Palindrome II — Solution in Python, Java & C++

Valid Palindrome II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on strings and greedy.

Valid Palindrome II is an easy coding problem on strings, greedy and two pointers.

  • Difficulty: Easy
  • Topics: Strings, Greedy, Two Pointers
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

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

Example 1

Input: s = "aba"
Output: true

Example 2

Input: s = "abca"
Output: true
Explanation: Delete the "c".

Example 3

Input: s = "abc"
Output: false

Constraints

  • 1 <= s.length <= 40
  • Lowercase English letters.

Hints for Valid Palindrome II

  1. Hint 1

    Two pointers as in a normal palindrome check.

  2. Hint 2

    On the first mismatch, you get one chance: skip the left char OR the right char, then require a perfect palindrome.

How to solve Valid Palindrome II

Run the ordinary two-pointer palindrome check. It either finishes cleanly — already a palindrome, zero deletions used — or it hits the first mismatch. At that point exactly one deletion is allowed, and only two candidates make sense: drop the left character or drop the right one. Test both as plain palindrome checks.

Approach

  1. Walk l from the front and r from the back while the characters match.
  2. If they always match, return true.
  3. On the first mismatch, check whether s[l+1 .. r] is a palindrome, or s[l .. r-1] is.
  4. Return true if either holds — that is the single allowed deletion.
  5. Otherwise return false.

Why it works

Everything outside the current window has already been matched in pairs, so it cannot be improved by a deletion — a deletion there would only unbalance the pairing. At the mismatch, the two characters cannot both stay, so any valid solution must remove one of them; there is no third option. Since only one deletion is permitted, both branches reduce to an exact palindrome check with no budget left, which is why the recursion never goes deeper than one level.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Both branches must be tried — dropping only the left character misses cases like "cbbcc" where the right one is the culprit.
  • The helper checks a plain palindrome with no remaining budget; allowing another deletion solves a different problem.
  • Only the first mismatch matters; continuing the scan past it conflates independent decisions.
  • Single characters and empty ranges are palindromes, which the loop bounds already handle.

Reference solution

Python

def validPalindrome(s: str) -> bool:
    def is_pal(l: int, r: int) -> bool:
        while l < r:
            if s[l] != s[r]:
                return False
            l += 1
            r -= 1
        return True

    l, r = 0, len(s) - 1
    while l < r:
        if s[l] != s[r]:
            return is_pal(l + 1, r) or is_pal(l, r - 1)
        l += 1
        r -= 1
    return True

Java

public static boolean validPalindrome(String s) {
    int l = 0, r = s.length() - 1;
    while (l < r) {
        if (s.charAt(l) != s.charAt(r)) return isPalVP(s, l + 1, r) || isPalVP(s, l, r - 1);
        l++;
        r--;
    }
    return true;
}

private static boolean isPalVP(String s, int lo, int hi) {
    while (lo < hi) {
        if (s.charAt(lo) != s.charAt(hi)) return false;
        lo++;
        hi--;
    }
    return true;
}

C++

bool isPalVP(const string& s, int lo, int hi) {
    while (lo < hi) {
        if (s[lo] != s[hi]) return false;
        lo++;
        hi--;
    }
    return true;
}

bool validPalindrome(string s) {
    int l = 0, r = (int) s.size() - 1;
    while (l < r) {
        if (s[l] != s[r]) return isPalVP(s, l + 1, r) || isPalVP(s, l, r - 1);
        l++;
        r--;
    }
    return true;
}

JavaScript

var validPalindrome = function(s) {
    function isPal(l, r) {
        while (l < r) {
            if (s[l] !== s[r]) return false;
            l++; r--;
        }
        return true;
    }
    let l = 0, r = s.length - 1;
    while (l < r) {
        if (s[l] !== s[r]) return isPal(l + 1, r) || isPal(l, r - 1);
        l++; r--;
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms