Valid Palindrome

Easy

Google

1 view

Topics:

StringsTwo Pointers

Problem: Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. A palindrome reads the same forwards and backward. For the purpose of this problem, we define empty string as valid palindrome.

Definition:

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.

Examples:

Input: "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome.
Input: "race a car" Output: false Explanation: "raceacar" is not a palindrome.
Input: " " Output: true Explanation: The string becomes empty after removing non-alphanumeric characters, which is a palindrome.

Constraints:

1 <= s.length <= 2 * 10^5
s consists only of printable ASCII characters.

Can you provide an efficient algorithm to determine if a given string meets these palindrome criteria?

Valid Palindrome

Easy

Google

1 view

Topics:

StringsTwo Pointers

Problem: Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. A palindrome reads the same forwards and backward. For the purpose of this problem, we define empty string as valid palindrome.

Definition:

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.

Examples:

Input: "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome.
Input: "race a car" Output: false Explanation: "raceacar" is not a palindrome.
Input: " " Output: true Explanation: The string becomes empty after removing non-alphanumeric characters, which is a palindrome.

Constraints:

1 <= s.length <= 2 * 10^5
s consists only of printable ASCII characters.

Can you provide an efficient algorithm to determine if a given string meets these palindrome criteria?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What characters are considered alphanumeric? Is the input guaranteed to be ASCII or can it include Unicode characters?
Should I handle null or undefined input, and if so, how should I respond?
Does the case-insensitive comparison need to handle locale-specific case conversions, or can I assume a simple lowercase conversion?
Are there any constraints on the length of the input string, or should I be aware of potential memory limitations for extremely long strings?
By 'empty string is a valid palindrome,' do you mean a string that is strictly empty (length 0), or a string containing only whitespace characters?

Brute Force Solution

Approach

The most straightforward way to check if something is a palindrome is to compare it to its reverse. This brute force method means directly reversing the input and checking if it matches the original.

Here's how the algorithm would work step-by-step:

First, take the input and create a reversed copy of it.
Next, compare the original input to the reversed copy.
If the original and reversed version are exactly the same, then it is a palindrome.
If they are different, it's not a palindrome.

Code Implementation

def is_palindrome_brute_force(input_string):
    # Create a reversed version of the input string
    reversed_string = input_string[::-1]

    # Compare the original with the reversed string
    # This is the core of the palindrome check
    if input_string == reversed_string:
        return True

    return False

Big(O) Analysis

Time Complexity

O(n) – Creating a reversed copy of the input string, which contains n characters, requires iterating through all n characters. Comparing the reversed string to the original string also involves examining each of the n characters in the worst case. Therefore, the overall time complexity is driven by operations proportional to the input size n, resulting in O(n).

Space Complexity

O(N) – The provided solution creates a reversed copy of the input. This reversed copy requires additional space to store the characters, and the size of this copy is directly proportional to the size of the original input, which we denote as N. Therefore, the auxiliary space used by this algorithm is N, as a new string of length N is created to store the reversed version. This leads to a space complexity of O(N).

Optimal Solution

Approach

The key is to efficiently compare the input from both ends, skipping irrelevant characters. We effectively ignore anything that isn't a letter or number, focusing only on the characters that matter for palindrome verification. This avoids unnecessary checks and speeds up the process.

Here's how the algorithm would work step-by-step:

First, transform the input by getting rid of any special characters, spaces, or punctuation. Also, make everything lowercase to ensure consistency.
Next, imagine having two pointers, one at the very beginning of the transformed input and another at the very end.
Compare the characters at both pointer locations. If they are different, it's not a palindrome, so we can stop and say it's invalid.
If the characters are the same, move the start pointer one step forward and the end pointer one step backward.
Keep repeating this process of comparing and moving the pointers until the two pointers meet in the middle or cross each other. If we reach this point, it means all the relevant characters matched, and it's a valid palindrome.

Code Implementation

def is_palindrome(input_string):
    processed_string = ''.join(character.lower() for character in input_string if character.isalnum())

    start_index = 0
    end_index = len(processed_string) - 1

    # Iterate until the pointers meet or cross
    while start_index < end_index:
        # Comparing characters from both ends
        if processed_string[start_index] != processed_string[end_index]:
            return False

        # Moving pointers towards the center
        start_index += 1
        end_index -= 1

    return True

Big(O) Analysis

Time Complexity

O(n) – The primary cost is driven by iterating through the input string once to filter non-alphanumeric characters and convert the string to lowercase, taking O(n) time, where n is the length of the input string. After the transformation, the two-pointer approach iterates through the transformed string to compare characters from both ends. In the worst case, it traverses up to half the string length, which is still O(n). Therefore, the overall time complexity is dominated by the initial string processing and the two-pointer comparisons, both of which are linear, resulting in O(n) time complexity.

Space Complexity

O(N) – The primary space complexity comes from the transformation of the input string in step 1, where we create a new string containing only alphanumeric characters in lowercase. This new string can potentially have the same length as the original input string in the worst case (e.g., when the input string contains only alphanumeric characters). Therefore, we use auxiliary space proportional to the input size N, where N is the length of the original input string.

Edge Cases

Case	How to Handle
Null or empty string	Return true, as an empty string is a valid palindrome by definition.
String with only one character	Return true, as a single character string is also a palindrome.
String with only non-alphanumeric characters	The pre-processing should reduce the string to empty, so return true.
String with mixed case alphanumeric characters	Convert the string to lowercase before processing to ensure case-insensitivity.
String with leading or trailing non-alphanumeric characters	The pre-processing should remove all non-alphanumeric characters at both ends.
String with all same alphanumeric characters	This is a valid palindrome, so the algorithm should return true.
String with alphanumeric characters and various non-alphanumeric separators	The pre-processing step must correctly remove all non-alphanumeric characters regardless of position.
Very long string to test performance	The solution should iterate linearly through the string, and should be efficient for large strings using a two-pointer approach.