Valid Palindrome LeetCode Problem 125 [Python Solution]

Valid Palindrome LeetCode Problem: A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Problem Overview

In this problem, we are given a string s, and our task is to determine if it is a palindrome.

A palindrome is a phrase that reads the same forwards and backward, ignoring spaces and considering uppercase and lowercase letters as equal.

For example, “A man, a plan, a canal: Panama” is a palindrome because, after converting it to lowercase and removing non-alphanumeric characters, it reads the same when reversed.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: After removing non-alphanumeric characters and converting to lowercase, the string becomes "amanaplanacanalpanama," which is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: After removing non-alphanumeric characters and converting to lowercase, the string becomes "raceacar," which is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: Since the input string is empty after removing non-alphanumeric characters, it is considered a palindrome.

Understanding the Constraints

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

The length of the string s is between 1 and 2 * 10^5.
The string s consists only of printable ASCII characters.

Now, let’s explore two different approaches to solving this problem:

Bruteforce Approach

One way to solve this problem is by constructing a new string that contains only alphanumeric characters from the original string.

After that, we compare the new string with its reverse to determine if it’s a palindrome.

Here’s how we can implement this approach in Python:

def isPalindrome(self, s: str) -> bool:
    new_s = ""
    for char in s:
        if char.isalnum():
            new_s += char.lower()
    return new_s == new_s[::-1]

In this solution, we iterate through each character in the string s.

If the character is alphanumeric, we append its lowercase version to the new_s string.

Finally, we check if new_s is equal to its reverse, which determines if the string is a palindrome.

Efficient Approach with Two Pointers

The brute force approach works, but it requires creating a new string, which consumes extra memory.

We can solve this problem more efficiently using two-pointers.

Here’s the Python code for the efficient approach:

Python Solution

View on GitHub ➹

def isPalindrome(self, s: str) -> bool:
    left, right = 0, len(s) - 1
    while left &lt; right:
        while left &lt; right and not self.alphanumeric(s[left]):
            left += 1
        while left &lt; right and not self.alphanumeric(s[right]):
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

def alphanumeric(self, char: str) -> bool:
    return (
        ord("a") &lt;= ord(char) &lt;= ord("z")
        or ord("A") &lt;= ord(char) &lt;= ord("Z")
        or ord("0") &lt;= ord(char) &lt;= ord("9")
    )

In this efficient approach, we use two pointers, left and right, initially pointing to the start and end of the string, respectively.

We then iterate while left is less than right. Within the loop, we skip non-alphanumeric characters by advancing left and right until we find alphanumeric characters.

We also check if the lowercase versions of the characters at left and right are not equal; if they’re not, we return False.

Otherwise, we continue comparing the next characters until we reach the middle of the string, at which point we return True.

Reasoning Behind Our Efficient Approach

The efficient approach uses two pointers to traverse the string from both ends, skipping non-alphanumeric characters and comparing the alphanumeric characters in a case-insensitive manner.

This approach has several advantages:

No Extra Memory: Unlike the brute force approach, which creates a new string, this approach uses constant extra memory, making it more memory-efficient.
Time Complexity: Both approaches have a time complexity of O(n), where n is the length of the input string. However, the efficient approach may perform fewer character comparisons in practice because it skips non-alphanumeric characters quickly.
Adaptable: The efficient approach can easily handle different variations of the problem, such as ignoring spaces and considering only alphabetic characters.

By understanding the constraints and implementing an efficient approach, we can solve the Valid Palindrome problem effectively.

Time and Space Complexity

Time Complexity: Both the brute force and efficient approaches have a time complexity of O(n), where n is the length of the input string. This is because we iterate through the entire string once.
Space Complexity: The brute force approach creates a new string, making its space complexity O(n). In contrast, the efficient approach uses constant extra memory, so its space complexity is O(1).

Constraints

The length of the string s is between 1 and 2 * 10^5.
The string s consists only of printable ASCII characters.

Edge Cases a Valid Solution Must Consider

When implementing a solution for this problem, it’s essential to consider edge cases and handle them correctly:

An empty string should be considered a palindrome.
The algorithm should handle uppercase and lowercase characters as equal when determining if a string is a palindrome.
Non-alphanumeric characters (e.g., spaces, punctuation) should be ignored when checking for palindromes.

By addressing these edge cases, you can ensure that your solution works correctly for a wide range of inputs.

Conclusion

In this article, we tackled the Valid Palindrome problem from LeetCode.

We explored two approaches: a brute force approach that constructs a new string and an efficient approach that uses two pointers to traverse the string.

The efficient approach, which uses constant extra memory and handles edge cases, is the preferred solution.

Remember that understanding the constraints, considering edge cases, and implementing an efficient algorithm are essential skills in solving programming problems.

Solve on LeetCode now.

I hope this guide has been helpful, and I encourage you to ask questions, make suggestions, and share your thoughts in the comments section.

Happy coding!