Valid Palindrome II Leetcode Problem 680 [Python Solution]

In this post, we’ll tackle the Valid Palindrome II problem from LeetCode.

The goal is to determine if a given string s can be transformed into a palindrome by removing at most one character.

Example:

• Input: s = "aba"
  Output: true
• Input: s = "abca"
  Output: true
  Explanation: You could delete the character ‘c’.
• Input: s = "abc"
  Output: false

Constraints:

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

Understanding the Constraints

Before we dive into the solution, let’s understand the problem constraints.

The string can have a maximum length of 105, and it contains only lowercase English letters.

This means we need an efficient solution that can handle relatively large inputs without exceeding time limits.

Valid Palindrome II LeetCode Problem Solution

Now, let’s discuss the solution to this problem.

The most straightforward approach would be to iterate through the string and, for each character, try removing it and check if the resulting substring is a palindrome.

However, this brute force approach would have a time complexity of O(n^2), which is not optimal.

A more efficient approach is to use a two-pointer technique.

We’ll initialize two pointers at the beginning and end of the string.

While these pointers are not equal, we’ll consider two scenarios:

1. Removing the left character:

We’ll create a substring starting from the second character (index 1) to the end and check if it’s a palindrome.

In Python, this can be done with the following code:

left_substring = s[1:]
is_palindrome = left_substring == left_substring[::-1]

2. Removing the right character:

Similarly, we’ll create a substring starting from the beginning to the second-to-last character and check if it’s a palindrome:

right_substring = s[:-1]
is_palindrome = right_substring == right_substring[::-1]

If either of these scenarios results in a palindrome, we return true.

If none of them does, we return false.

This approach has a time complexity of O(n).

Python Code Solution

Here’s the Python code that implements the efficient approach:

class Solution:
    def validPalindrome(self, s: str) -> bool:
        i, j = 0, len(s) - 1

        while i < j:
            if s[i] == s[j]:
                i += 1
                j -= 1
            else:
                return self.is_palindrome(s, i + 1, j) or self.is_palindrome(s, i, j - 1)
        return True

    def is_palindrome(self, s: str, i: int, j: int) -> bool:
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

Time and Space Complexity

The time complexity of this solution is O(n) because we perform a single pass through the string, and the space complexity is O(1), as we only use a constant amount of extra space.

Reasoning Behind Our Approach

We use a two-pointer technique to efficiently search for a palindrome.

By considering scenarios where we either remove the left or right character, we avoid the need to explore every possible character removal, which would result in a less efficient O(n^2) solution.

Related Interview Questions By Company:

• Diameter Of Binary Tree LeetCode
• Path Sum LeetCode
• Intersection Of Two Linked Lists LeetCode

Related Interview Questions By Difficulty:

• Merge Sorted Array LeetCode
• Remove Duplicates From Sorted Array LeetCode
• Number Of Subsequences That Satisfy The Given Sum Condition LeetCode

Related Interview Questions By Category:

• Online Stock Span LeetCode
• Palindrome Number LeetCode
• Concatenation Of Array LeetCode

Conclusion

In this blog post, we tackled the Valid Palindrome II problem from LeetCode.

We discussed the problem, the constraints, and provided an efficient Python solution using a two-pointer technique.

By following this approach, we can determine if a given string can be transformed into a palindrome by removing at most one character.

We hope this post was helpful in understanding the problem and its solution.

If you found this content useful, please consider liking and subscribing.

Your support means a lot to us.

Feel free to ask questions, make suggestions, and share this content with others who might find it valuable.

For the full problem details and more, you can visit the LeetCode question here.

Now, it’s your turn to tackle this problem and explore more exciting coding challenges!