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 <= 40Lowercase English letters.
Hints for Valid Palindrome II
Hint 1
Two pointers as in a normal palindrome check.
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
- Walk
lfrom the front andrfrom the back while the characters match. - If they always match, return
true. - On the first mismatch, check whether
s[l+1 .. r]is a palindrome, ors[l .. r-1]is. - Return
trueif either holds — that is the single allowed deletion. - 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 TrueJava
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