Log inSign up
easyleetcodeNot Started

Valid Palindrome II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

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

Example 1:

Input: s = "aba"
Output: true
Explanation: The string is already a palindrome.

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character c to get "aba", which is a palindrome.

Example 3:

Input: s = "abc"
Output: false
Explanation: Deleting any single character does not make the string a palindrome.

Constraints:

  • 1 <= s.length <= 105
  • s consists of lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply greedy two pointers to fault-tolerant palindrome problems.
  • Branch into two deterministic sub-checks upon the first mismatch.
  • Prove why checking beyond the first mismatch is unnecessary.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Determining if a string can become a palindrome with at most K deletions (here K = 1).
  • Handling symmetric matching with fault tolerance.

Algorithmic Decision Tree:

  • Determining if a string can become a palindrome with at most K deletions (here K = 1).
  • Handling symmetric matching with fault tolerance.

Connected Patterns:

Valid PalindromeValid Palindrome IIILongest Palindromic Subsequence

1. Try Deleting Every Character

Intuition

First check if s is already a palindrome. If not, iterate i from 0 to N - 1, constructing t = s[0...i-1] + s[i+1...N-1]. Check if t is a palindrome. If any t is a palindrome, return true; else false.

When to apply: Basic baseline comparison.

Algorithm

  1. If s is palindrome: return true.
  2. For i from 0 to s.length - 1:
  3. t = s.substr(0, i) + s.substr(i + 1).
  4. If t is palindrome: return true.
  5. Return false.

Exhaustive Deletion Testing Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b, c, a]
Current operationSTEP 1 OF 6
Observation: Test deleting character at index 0 ('a')
Visual state
Values and pointers at this exact step
array
S
a
b
c
a
0
↑ DELETE IDX 0
1
2
3
Variables at this step
Deleted
s[0]='a'
Sub
bca
Is Palindrome
false
Check / comparison
Candidate 0: Delete s[0]='a'. Remaining string sub = "bca".
Decision / next transition
Check if "bca" is palindrome: "bca" != "acb". Fails.
Why this step matters

Observation: Test deleting character at index 0 ('a'). Substring is "bca".

Decision: "bca" !== "acb". Deleting index 0 does not yield a palindrome.

Invariant: Candidate 0 rejected.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5 bool isPal(const std::string& s) {
6 int l = 0, r = s.size() - 1;
7 while (l < r) {
8 if (s[l++] != s[r--]) return false;
9 }
10 return true;
11 }
12public:
13 bool validPalindrome(std::string s) {
14 if (isPal(s)) return true;
15 int n = s.size();
16 for (int i = 0; i < n; ++i) {
17 std::string t = s.substr(0, i) + s.substr(i + 1);
18 if (isPal(t)) return true;
19 }
20 return false;
21 }
22};
23
24int main() {
25 Solution sol;
26 std::cout << (sol.validPalindrome("abca") ? "true" : "false") << std::endl; // true
27 std::cout << (sol.validPalindrome("abc") ? "true" : "false") << std::endl; // false
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N^2) — N iterations, each performing an O(N) string creation and palindrome check.
  • Space complexity: O(N)

Why Brute Force Doesn't Scale:

Reduces search tree from O(N) possibilities to exactly two deterministic sub-scans.

Passes indices (l, r) to avoid substring allocations.

2. Recursive Fault-Tolerant Search

Intuition

Define helper(l, r, k) where k is the remaining allowed deletions (initially 1). While l < r: if s[l] == s[r], advance l++, r--. Else if k > 0, return helper(l + 1, r, k - 1) || helper(l, r - 1, k - 1). Else return false.

When to apply: When generalizing to at most K deletions.

Algorithm

  1. Helper check(s, l, r, k):
  2. While l < r:
  3. If s[l] == s[r]: l++; r--.
  4. Else if k > 0: return check(s, l + 1, r, k - 1) || check(s, l, r - 1, k - 1).
  5. Else: return false.
  6. Return true.
  7. Call check(s, 0, s.length - 1, 1).

Recursive Fault-Tolerant Search Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b, c, a]
Current operationSTEP 1 OF 6
Observation: Frame 1: check(0, 3, chance=1)
Visual state
Values and pointers at this exact step
array
S
a
b
c
a
0
↑ l=0
1
2
3
↑ r=3
Variables at this step
l
0
r
3
Chance
1
Match
true
Check / comparison
Call check(l=0, r=3, chance=1). s[0] ('a') == s[3] ('a'). Match.
Decision / next transition
Characters match. Advance l to 1, decrement r to 2.
Why this step matters

Observation: Frame 1: check(0, 3, chance=1). s[0] == s[3] == 'a'.

Decision: Match confirmed. Advance l -> 1, r -> 2.

Invariant: Outer characters match with chance remaining = 1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5 bool check(const std::string& s, int l, int r, int k) {
6 while (l < r) {
7 if (s[l] == s[r]) {
8 l++; r--;
9 } else if (k > 0) {
10 return check(s, l + 1, r, k - 1) || check(s, l, r - 1, k - 1);
11 } else {
12 return false;
13 }
14 }
15 return true;
16 }
17public:
18 bool validPalindrome(std::string s) {
19 return check(s, 0, (int)s.size() - 1, 1);
20 }
21};
22
23int main() {
24 Solution sol;
25 std::cout << (sol.validPalindrome("abca") ? "true" : "false") << std::endl; // true
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(N) — Branches at most once, performing O(N) work across branches.
  • Space complexity: O(1) recursion depth (at most 2 frames)

3. Two Pointers with Substring Branching (Optimal)

Intuition

Initialize left = 0, right = s.length - 1. While left < right: if s[left] == s[right], left++, right--. Otherwise, return isPal(s, left + 1, right) || isPal(s, left, right - 1). If loop finishes with zero mismatches, return true.

When to apply: The standard gold standard solution.

Algorithm

  1. Initialize left = 0, right = s.length - 1.
  2. While left < right:
  3. If s[left] == s[right]:
  4. left++; right--.
  5. Else:
  6. Return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1).
  7. Return true.

Greedy Mismatch Branching with Single Deletion Allowance

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b, c, a]
Current operationSTEP 1 OF 6
Observation: Initialize two pointers at opposite extremes: left = 0 ('a'), right = 3 ('a')
Visual state
Values and pointers at this exact step
array
S
a
b
c
a
0
↑ L=0 ('a')
1
2
3
↑ R=3 ('a')
Variables at this step
L Pointer
0 ('a')
R Pointer
3 ('a')
Deletions Left
1
Match
true
Check / comparison
s[0] ('a') == s[3] ('a'). Match!
Decision / next transition
Advance L to 1, R to 2. No deletion used yet.
Why this step matters

Observation: Initialize two pointers at opposite extremes: left = 0 (a), right = 3 (a).

Decision: s[0] === s[3]. Match successful. Advance pointers: left = 1, right = 2.

Invariant: Outer boundary is valid without using any character deletion.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5 bool isPalindromeRange(const std::string& s, int l, int r) {
6 while (l < r) {
7 if (s[l++] != s[r--]) return false;
8 }
9 return true;
10 }
11public:
12 bool validPalindrome(std::string s) {
13 int left = 0, right = (int)s.size() - 1;
14 while (left < right) {
15 if (s[left] == s[right]) {
16 left++;
17 right--;
18 } else {
19 return isPalindromeRange(s, left + 1, right) || isPalindromeRange(s, left, right - 1);
20 }
21 }
22 return true;
23 }
24};
25
26int main() {
27 Solution sol;
28 std::cout << (sol.validPalindrome("aba") ? "true" : "false") << std::endl; // true
29 std::cout << (sol.validPalindrome("abca") ? "true" : "false") << std::endl; // true
30 std::cout << (sol.validPalindrome("abc") ? "true" : "false") << std::endl; // false
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N) strictly — At most two scans of length at most N; memory is strictly constant.
  • Space complexity: O(1) extra space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Delete Every Character Brute ForceO(N^2)O(N)Tests all N possible deletions.Quadratic time TLE on 105 length strings.
2.Two Pointers with Branching on First Mismatch (Optimal)OptimalO(N)O(1) extra spaceStrictly linear time, at most two O(N) sub-verifications, O(1) memory.None.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Only testing one deletion branch (e.g. only skipping left pointer) which fails on inputs like cupu or abca.

Pitfall 2:

Allocating new sliced strings for the sub-palindrome check.

Crucial Edge Cases to Validate:

  • Already a palindrome (s = racecar): Zero mismatches encountered, returns true.
  • Single character string (s = a): left=0, right=0; loop terminates, returns true.
  • Deletion required at extreme ends (e.g. s = ab): Mismatch at left=0, right=1: isPal(1, 1) returns true.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the greedy choice: if outer characters match, neither of them should be deleted.
  2. Show helper isPal(l, r) using indices for O(1) space.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is it guaranteed that we only need to branch on the FIRST mismatch?

Back to DSA Sheet