Problem Statement

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

LeetCode

• https://leetcode.com/problems/valid-palindrome-ii/

Constraints

1 <= s.length <= 10^5
s consists of lowercase English letters.

Examples

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

Different Approaches

1️⃣ Brute Force Approach

🔍 Intuition:

• Try removing each character one by one.
• For each deletion, check if the resulting string is a palindrome.

 Code:

class Solution {
public:
    bool isPalindrome(string& s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            if (s[left++] != s[right--]) return false;
        }
        return true;
    }

    bool validPalindrome(string s) {
        if (isPalindrome(s)) return true;

        for (int i = 0; i < s.length(); i++) {
            string temp = s.substr(0, i) + s.substr(i + 1);
            if (isPalindrome(temp)) return true;
        }

        return false;
    }
};

Complexity Analysis:

• Time Complexity:O(n^2)
  • Checking n substring each of length up to n
• Space Complexity:O(n)
  • For each substring copy

2️⃣ Two Pointers Approach

🔍 Intuition:

• A palindrome reads the same forward and backward.
• You are allowed to remove at most one character, so as soon as a mismatch occurs, you have 2 choices:
  • Skip the left character
  • Skip the right character
• If either results in a palindrome, return true.

🧠 Algorithm:

1. Use two pointers: left = 0, right = n - 1
2. If characters match, move inward.
3. On mismatch:
   1. Try skipping left → check isPalindrome(left+1, right)
   2. Try skipping right → check isPalindrome(left, right-1)
4. Return true if either is a palindrome.

Code:

class Solution {
public:

    // Helper function to check if a given substring is a palindrome
    // It takes a string `s` and two indices: left and right
    bool isPalindrome(string& s, int left, int right) {
        while (left < right) {
            // If characters at left and right don't match, it's not a palindrome
            if (s[left] != s[right]) return false;

            // Move inward
            left++;
            right--;
        }
        // If loop completes, it's a palindrome
        return true;
    }

    // Main function to check if the string can be a palindrome
    // by removing at most one character
    bool validPalindrome(string s) {
        int left = 0;
        int right = s.length() - 1;

        // Use two pointers from both ends
        while (left < right) {
            // If characters match, move both pointers inward
            if (s[left] == s[right]) {
                left++;
                right--;
            } else {
                // If characters don't match:
                // Try skipping one character either from left or right,
                // and check if the rest forms a palindrome

                // Case 1: skip the left character (left + 1)
                // Case 2: skip the right character (right - 1)
                // If either case returns true, it's valid
                return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
            }
        }

        // If no mismatches are found or valid by removing one character
        return true;
    }
};

⏱ Complexity Analysis:

• Time Complexity:O(n) — one pass + possible one more partial pass
• Space Complexity: O(1)

3️⃣ Recursive Approach

🔍 Intuition:

• Use recursion to try both deletions and check for validity.
• At each mismatch, recurse with one character skipped.

Code:

class Solution {
public:

    // Recursive helper function to check if a string can be a palindrome
    // with at most one character deletion
    bool helper(string& s, int left, int right, int deleteCount) {
        // If we've already deleted more than one character, return false
        if (deleteCount > 1) return false;

        // Use two pointers to compare characters from both ends
        while (left < right) {
            if (s[left] == s[right]) {
                // If characters match, move both pointers inward
                left++;
                right--;
            } else {
                // If characters don't match:
                // Try both deletion options:
                // 1. Delete character at `left` and recurse
                // 2. Delete character at `right` and recurse
                // Increment deleteCount in each recursive call
                return helper(s, left + 1, right, deleteCount + 1) ||
                       helper(s, left, right - 1, deleteCount + 1);
            }
        }

        // If loop completes or a valid path is found, return true
        return true;
    }

    // Main function to start the process with 0 deletions so far
    bool validPalindrome(string s) {
        return helper(s, 0, s.length() - 1, 0);
    }
};

⏱ Complexity Analysis:

• Time Complexity:O(n)
  • Worst case O(n) (limited depth recursion)
• Space Complexity:O(n) (recursion stack in worst case)