DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Valid Palindrome II - Solution
Solutions and explanations
Link to Problem StatementView on GitHubWatch Video

Video Explanation

We recursively compare characters from both ends of the string, allowing at most one deletion by branching into two recursive paths when a mismatch occurs.

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_palindrome(left, right, deletion_used):
            if left >= right:
                return True
            if s[left] == s[right]:
                return is_palindrome(left + 1, right - 1, deletion_used) 
            if deletion_used:
                return False
            return is_palindrome(left + 1, right, True) or is_palindrome(left, right - 1, True)
            
        return is_palindrome(0, len(s) - 1, False)

Complexity Analysis

Here, n is the length of the input string.

  • Time Complexity: O(n) – At most one character can be skipped, so the recursion explores at most two paths, each scanning up to n characters.
  • Space Complexity: O(n) – Extra space is used by the recursion stack, with a maximum depth of up to n.

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_palindrome(left, right):
            return s[left:right + 1] == s[left:right + 1][::-1]
        
        left, right = 0, len(s) - 1
        while left < right:
            if s[left] != s[right]:
                return is_palindrome(left, right - 1) or is_palindrome(left + 1, right)
            left += 1
            right -= 1
        return True

Complexity Analysis

Here, n is the length of the input string.

  • Time Complexity: O(n) – Since each character is scanned at most twice, the total operations are 2n, which is still O(n).
  • Space Complexity: O(n) – Slicing and reversing create new substrings, using up to O(n) additional memory.

We traverse the input string with two pointers from both ends.
On a mismatch, we check both possible substrings — one with the left character removed and one with the right (using a helper function that continues the two-pointer comparison on the remaining characters).

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_palindrome(left, right):
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True
        
        left, right = 0, len(s) - 1
        while left < right:
            if s[left] != s[right]:
                return is_palindrome(left, right - 1) or is_palindrome(left + 1, right)
            left += 1
            right -= 1
        return True

Complexity Analysis

Here, n is the length of the input string.

  • Time Complexity: O(n) – Each character is scanned at most twice, resulting in 2n operations, which simplifies to O(n).
  • Space Complexity: O(1)