Leetcode – Valid Palindrome II Solution in Python

Spread the love

Introduction

Palindromes are a classic and intriguing concept in computer science and linguistics. The problem “Valid Palindrome II” on Leetcode presents an interesting twist on standard palindrome checking, and understanding how to tackle this problem is essential for mastering string manipulation algorithms. This article provides a detailed walkthrough of the problem, the underlying concepts required to solve it, and different algorithms for tackling the problem with Python.

Problem Statement

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example:

Input: "abca"

Output: True

Explanation: You could delete the character ‘c’.

Note:

  • The string will only contain lowercase characters.
  • The maximum length of the string is 50,000.

Concepts Required

1. Palindromes

A palindrome is a word, number, or other sequences of characters that reads the same forward and backward (ignoring spaces, punctuation, and capitalization).

2. Two Pointers Technique

The two pointers technique is an approach where two pointers iterate through an array (or a string) from the beginning and end, moving towards each other. This technique is especially useful when dealing with array or string manipulation problems.

Solution

1. Two Pointers with Recursion

In this approach, we will use the two pointers technique to check if the string can be a palindrome. The twist in this problem, compared to standard palindrome checking, is that we can remove at most one character.

  1. Initialize two pointers, left and right, at the beginning and end of the string, respectively.
  2. Compare the characters at left and right positions.
  3. If they are equal, move left one step forward and right one step backward.
  4. If they are not equal, check two cases: a. Skip the character at the left pointer and see if the rest of the string is a palindrome. b. Skip the character at the right pointer and see if the rest of the string is a palindrome.
  5. If one of the cases in step 4 is a palindrome, the entire string can become a palindrome by removing a character. Otherwise, it cannot.
  6. Return True if it can be a palindrome, otherwise return False.
def validPalindrome(s):
    def is_palindrome_range(i, j):
        return all(s[k] == s[j-k+i] for k in range(i, j))
    
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return is_palindrome_range(left+1, right) or is_palindrome_range(left, right-1)
        left, right = left + 1, right - 1
        
    return True

Time Complexity:

  • O(n), where n is the length of the input string.

Space Complexity:

  • O(1), as we are using a constant amount of extra space.

2. Dynamic Programming Approach (Optional, Not Optimal for this Problem)

Though dynamic programming is not the most optimal solution for this problem, understanding its application can be informative for solving more complex problems.

  1. Create a 2D boolean array dp, where dp[i][j] is True if the substring s[i:j+1] can be a palindrome.
  2. Initialize all dp[i][i] as True.
  3. Iterate through the string and fill in the dp array.
  4. Use the dp array to check if the string can be a palindrome by removing at most one character.
def validPalindrome(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    
    for i in range(n):
        dp[i][i] = True
        
    deleted = False
    for length in range(2, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] or length == 2
            else:
                deleted = True
    
    return dp[0][n-1] or (dp[0][n-2] and deleted) or (dp[1][n-1] and deleted)

Time Complexity:

  • O(n^2), where n is the length of the input string.

Space Complexity:

  • O(n^2), as we are using an additional 2D array to store the states.

Conclusion

The “Valid Palindrome II” problem is a classic string manipulation problem with an interesting twist. It requires understanding the concept of palindromes and employing the two pointers technique effectively. The most optimal approach involves using two pointers with recursion to check for the possibility of forming a palindrome by removing at most one character.

Leave a Reply