Jobs

Interviews

Discussions

Valid Palindrome

Easy

Spotify

0 views

Topics:

Two PointersStrings

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.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

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

Valid Palindrome

Easy

Spotify

0 views

Topics:

Two PointersStrings

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

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

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

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 it strictly limited to a-z, A-Z, and 0-9 or are other unicode characters considered alphanumeric?
How should I handle non-ASCII characters in the input string?
Besides an empty string, are there any other special cases for the input string that I should be aware of?
Is the comparison case-insensitive only for English alphabets, or should I handle case-insensitive comparisons for all unicode characters?
Are there any memory constraints I should consider if the input string is extremely large?

Brute Force Solution

Approach

The brute force approach for checking if something is a palindrome means we'll examine every possible pairing of characters. We'll look at the original string and see if it reads the same forwards and backward, ignoring non-letter stuff. This involves a direct, character-by-character comparison.

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

First, get rid of anything that's not a letter or a number, like spaces or symbols. Make it all lowercase too.
Now, start by looking at the first letter.
Compare it to the last letter. If they're not the same, it's not a palindrome.
If they are the same, move to the second letter and the second-to-last letter.
Keep comparing letters from the beginning and the end, working your way to the middle.
If you get to the middle without finding any mismatches, then it's a palindrome.

Code Implementation

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

    left_index = 0
    right_index = len(processed_string) - 1

    # Compare characters from both ends until indices meet

    while left_index < right_index:
        if processed_string[left_index] != processed_string[right_index]:
            return False

        left_index += 1
        right_index -= 1

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm first iterates through the input string of length n to remove non-alphanumeric characters and convert it to lowercase, which takes O(n) time. Then, it compares characters from both ends of the processed string towards the middle. In the worst case, it will compare approximately n/2 character pairs. Therefore, the character comparison step also takes O(n) time. Combining these two linear operations, the overall time complexity is O(n) + O(n) which simplifies to O(n).

Space Complexity

O(N) – The algorithm first creates a modified string by removing non-alphanumeric characters and converting the remaining characters to lowercase. This results in a new string whose length could be up to N, where N is the length of the original input string. This new string occupies O(N) auxiliary space. After creating the modified string, only constant space is used for index comparisons. Therefore, the overall space complexity is dominated by the modified string creation.

Optimal Solution

Approach

The goal is to check if a sentence reads the same forwards and backward, ignoring unimportant details like capitalization and punctuation. Instead of comparing the entire sentence directly, we can focus on comparing only the important parts from both ends moving inward. This avoids unnecessary comparisons and speeds up the process.

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

First, clean up the sentence by getting rid of anything that's not a letter or a number and convert everything to the same case (either all lowercase or all uppercase).
Next, imagine pointers at the very beginning and the very end of the cleaned-up sentence.
Compare the characters at each of the pointer positions.
If the characters match, move both pointers closer to the middle: the starting pointer moves forward, and the ending pointer moves backward.
Keep comparing characters and moving the pointers until they either meet in the middle or cross over each other.
If at any point the characters don't match, it's not a palindrome. Otherwise, if you've made it all the way to the middle without finding any mismatches, the sentence is a valid palindrome.

Code Implementation

def is_valid_palindrome(input_string):
    cleaned_string = ''.join(character.lower() for character in input_string if character.isalnum())

    starting_index = 0
    ending_index = len(cleaned_string) - 1

    # Compare characters from both ends moving inward.
    while starting_index < ending_index:
        if cleaned_string[starting_index] != cleaned_string[ending_index]:
            return False

        starting_index += 1
        ending_index -= 1

    # If the loop finishes, it's a valid palindrome.
    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm first cleans the input string of length n, iterating through it once to remove non-alphanumeric characters and convert to lowercase. This cleaning process takes O(n) time. Then, it uses two pointers to traverse the cleaned string from both ends, comparing characters until the pointers meet in the middle. This comparison also iterates through at most n/2 elements of the cleaned string, making it another O(n) operation. Since O(n) + O(n) simplifies to O(n), the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm first cleans the input string, creating a new string containing only alphanumeric characters in lowercase. This cleaned string can have at most the same number of characters as the original input string. Therefore, auxiliary space is used to store this cleaned string, which could potentially have a length of N, where N is the length of the input string. The two pointers used for comparison take constant space. Thus, the dominant factor is the space for the cleaned string, which leads to O(N) space complexity.

Edge Cases

Case	How to Handle
Empty string	The problem states an empty string is a valid palindrome, so return true.
Null string	Handle a null string input, typically by returning true (treating it as empty) or throwing an IllegalArgumentException based on requirements.
String with only non-alphanumeric characters	After filtering, the string becomes empty, which should be handled as a valid palindrome returning true.
String with a single alphanumeric character	A single character is always a palindrome, return true.
String with two identical alphanumeric characters	This is a valid palindrome, return true.
String with two different alphanumeric characters	This is not a valid palindrome, return false.
String with mixed case alphanumeric characters (e.g., 'Racecar')	Convert the string to lowercase before comparison to handle case-insensitivity.
String with very long length approaching system limits	Ensure the solution has optimal time complexity O(n) and doesn't cause stack overflow with recursive calls; iterative two-pointer is preferred.

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 it strictly limited to a-z, A-Z, and 0-9 or are other unicode characters considered alphanumeric?
How should I handle non-ASCII characters in the input string?
Besides an empty string, are there any other special cases for the input string that I should be aware of?
Is the comparison case-insensitive only for English alphabets, or should I handle case-insensitive comparisons for all unicode characters?
Are there any memory constraints I should consider if the input string is extremely large?

Brute Force Solution

Approach

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

First, get rid of anything that's not a letter or a number, like spaces or symbols. Make it all lowercase too.
Now, start by looking at the first letter.
Compare it to the last letter. If they're not the same, it's not a palindrome.
If they are the same, move to the second letter and the second-to-last letter.
Keep comparing letters from the beginning and the end, working your way to the middle.
If you get to the middle without finding any mismatches, then it's a palindrome.

Code Implementation

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

    left_index = 0
    right_index = len(processed_string) - 1

    # Compare characters from both ends until indices meet

    while left_index < right_index:
        if processed_string[left_index] != processed_string[right_index]:
            return False

        left_index += 1
        right_index -= 1

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, clean up the sentence by getting rid of anything that's not a letter or a number and convert everything to the same case (either all lowercase or all uppercase).
Next, imagine pointers at the very beginning and the very end of the cleaned-up sentence.
Compare the characters at each of the pointer positions.
If the characters match, move both pointers closer to the middle: the starting pointer moves forward, and the ending pointer moves backward.
Keep comparing characters and moving the pointers until they either meet in the middle or cross over each other.
If at any point the characters don't match, it's not a palindrome. Otherwise, if you've made it all the way to the middle without finding any mismatches, the sentence is a valid palindrome.

Code Implementation

def is_valid_palindrome(input_string):
    cleaned_string = ''.join(character.lower() for character in input_string if character.isalnum())

    starting_index = 0
    ending_index = len(cleaned_string) - 1

    # Compare characters from both ends moving inward.
    while starting_index < ending_index:
        if cleaned_string[starting_index] != cleaned_string[ending_index]:
            return False

        starting_index += 1
        ending_index -= 1

    # If the loop finishes, it's a valid palindrome.
    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string	The problem states an empty string is a valid palindrome, so return true.
Null string	Handle a null string input, typically by returning true (treating it as empty) or throwing an IllegalArgumentException based on requirements.
String with only non-alphanumeric characters	After filtering, the string becomes empty, which should be handled as a valid palindrome returning true.
String with a single alphanumeric character	A single character is always a palindrome, return true.
String with two identical alphanumeric characters	This is a valid palindrome, return true.
String with two different alphanumeric characters	This is not a valid palindrome, return false.
String with mixed case alphanumeric characters (e.g., 'Racecar')	Convert the string to lowercase before comparison to handle case-insensitivity.
String with very long length approaching system limits	Ensure the solution has optimal time complexity O(n) and doesn't cause stack overflow with recursive calls; iterative two-pointer is preferred.