Jobs

Interviews

Discussions

Valid Palindrome

#3 Most AskedEasy

Valid Palindrome #3 Most Asked

Easy

Bank of America

20 views

Topics:

StringsTwo Pointers

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.

Try coding it in LeetCode

Valid Palindrome

#3 Most AskedEasy

Valid Palindrome #3 Most Asked

Easy

Bank of America

20 views

Topics:

StringsTwo Pointers

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.

Try coding it in LeetCode

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 is the expected maximum length of the input string 's'?
Are there any specific characters that should be considered 'non-alphanumeric' beyond standard punctuation and symbols?
Should I consider Unicode characters or only ASCII alphanumeric characters?
If the input string is empty or contains only non-alphanumeric characters, what should be the expected boolean return value?
Is it possible for the input string to contain characters that are not part of the standard character set, such as control characters?

Brute Force Solution

Approach

To check if a phrase is a palindrome using brute force, we essentially want to compare the phrase forwards and backwards. The simplest way is to create a reversed version of the phrase and then directly compare it to the original.

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

Take the original phrase and make a brand new phrase that is its exact opposite.
Imagine writing the original phrase down and then writing the reversed phrase down right below it.
Now, compare the letters of the original phrase with the letters of the reversed phrase, one by one, from the very beginning to the very end.
If every single letter matches up perfectly in the same position, then the original phrase is a palindrome.
If you find even one spot where the letters don't match, then it's not a palindrome.

Code Implementation

def is_palindrome_brute_force(input_phrase):
    reversed_phrase = input_phrase[::-1]

    # To determine if it's a palindrome, we must compare the original string with its reversed version.
    if input_phrase == reversed_phrase:
        # If every character matches in the same position, it is a palindrome.
        return True
    else:
        # If any character does not match, it is not a palindrome.
        return False

Big(O) Analysis

Time Complexity

O(n) – To determine if a phrase is a palindrome, we first construct a reversed version of the original phrase. This operation involves iterating through each character of the original phrase once to build the reversed string. Then, we compare the original phrase with the reversed phrase character by character. This comparison also requires iterating through all characters of the phrase once. Since both constructing the reversed string and comparing it take linear time relative to the length of the phrase (let's call this length 'n'), the total time complexity is proportional to n + n, which simplifies to O(n).

Space Complexity

O(n) – The brute-force approach involves creating a brand new phrase that is the exact opposite of the original. If the original phrase has a length of N characters, this reversed phrase will also require N characters of storage. Therefore, the auxiliary space complexity is directly proportional to the input size N, leading to O(n).

Optimal Solution

Approach

To check if a phrase is a palindrome, we can compare the characters from the beginning and end simultaneously. If they always match as we move inwards, the phrase is a palindrome.

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

Imagine you have pointers, one at the very start of the phrase and another at the very end.
Move both pointers towards the middle, one step at a time, ignoring any characters that aren't letters or numbers.
At each step, check if the letter or number pointed to by the start pointer is the same as the one pointed to by the end pointer, after making sure they are both in the same case (like all lowercase).
If at any point the characters don't match, you know immediately that the phrase isn't a palindrome, and you can stop.
If the pointers meet or cross each other without finding any mismatches, then the entire phrase is a palindrome.

Code Implementation

def is_palindrome(input_string):
    left_pointer = 0
    right_pointer = len(input_string) - 1

    while left_pointer < right_pointer:
        # Advance left pointer past non-alphanumeric characters.
        if not input_string[left_pointer].isalnum():
            left_pointer += 1
            continue

        # Advance right pointer past non-alphanumeric characters.
        if not input_string[right_pointer].isalnum():
            right_pointer -= 1
            continue

        # Compare characters, ignoring case.
        if input_string[left_pointer].lower() != input_string[right_pointer].lower():
            return False

        # Move pointers towards the center.
        left_pointer += 1
        right_pointer -= 1

    # If pointers meet or cross without mismatches, it's a palindrome.
    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string with two pointers, one starting from the beginning and the other from the end, moving towards the middle. In the worst case, each pointer will traverse approximately half of the string's length. Each character comparison and skip operation takes constant time. Therefore, the total number of operations is directly proportional to the length of the string, n, leading to a time complexity of O(n).

Space Complexity

O(1) – The solution uses a constant amount of extra space. This is because it only requires two pointers (variables) to track the start and end of the phrase, regardless of the input phrase's length. No additional data structures are created that grow with the input size N. Therefore, the auxiliary space complexity remains constant.

Edge Cases

Case	How to Handle
Empty string input	An empty string is considered a palindrome, so the function should return true.
String with only non-alphanumeric characters	After processing, the string becomes empty, which is a valid palindrome and should return true.
String with a single alphanumeric character	A single character string is always a palindrome, so the function should return true.
String with mixed case letters and numbers	All uppercase letters should be converted to lowercase, and only alphanumeric characters should be considered for the palindrome check.
String with all identical alphanumeric characters	Such strings are always palindromes, and the algorithm should correctly identify this.
Very long strings	The solution should be efficient in terms of time and space complexity to handle potentially large inputs without exceeding typical memory or time limits.
String with leading or trailing non-alphanumeric characters	These characters should be ignored during the processing and palindrome check.
String with unicode characters that are alphanumeric	Ensure the alphanumeric check correctly identifies and processes alphanumeric characters across different Unicode ranges if applicable, though standard ASCII is usually assumed.

Empty string input

How to Handle:

An empty string is considered a palindrome, so the function should return true.

String with only non-alphanumeric characters

How to Handle:

After processing, the string becomes empty, which is a valid palindrome and should return true.

String with a single alphanumeric character

How to Handle:

A single character string is always a palindrome, so the function should return true.

String with mixed case letters and numbers

How to Handle:

All uppercase letters should be converted to lowercase, and only alphanumeric characters should be considered for the palindrome check.

String with all identical alphanumeric characters

How to Handle:

Such strings are always palindromes, and the algorithm should correctly identify this.

Very long strings

How to Handle:

The solution should be efficient in terms of time and space complexity to handle potentially large inputs without exceeding typical memory or time limits.

String with leading or trailing non-alphanumeric characters

How to Handle:

These characters should be ignored during the processing and palindrome check.

String with unicode characters that are alphanumeric

How to Handle:

Ensure the alphanumeric check correctly identifies and processes alphanumeric characters across different Unicode ranges if applicable, though standard ASCII is usually assumed.

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 is the expected maximum length of the input string 's'?
Are there any specific characters that should be considered 'non-alphanumeric' beyond standard punctuation and symbols?
Should I consider Unicode characters or only ASCII alphanumeric characters?
If the input string is empty or contains only non-alphanumeric characters, what should be the expected boolean return value?
Is it possible for the input string to contain characters that are not part of the standard character set, such as control characters?

Brute Force Solution

Approach

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

Take the original phrase and make a brand new phrase that is its exact opposite.
Imagine writing the original phrase down and then writing the reversed phrase down right below it.
Now, compare the letters of the original phrase with the letters of the reversed phrase, one by one, from the very beginning to the very end.
If every single letter matches up perfectly in the same position, then the original phrase is a palindrome.
If you find even one spot where the letters don't match, then it's not a palindrome.

Code Implementation

def is_palindrome_brute_force(input_phrase):
    reversed_phrase = input_phrase[::-1]

    # To determine if it's a palindrome, we must compare the original string with its reversed version.
    if input_phrase == reversed_phrase:
        # If every character matches in the same position, it is a palindrome.
        return True
    else:
        # If any character does not match, it is not a palindrome.
        return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

To check if a phrase is a palindrome, we can compare the characters from the beginning and end simultaneously. If they always match as we move inwards, the phrase is a palindrome.

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

Imagine you have pointers, one at the very start of the phrase and another at the very end.
Move both pointers towards the middle, one step at a time, ignoring any characters that aren't letters or numbers.
At each step, check if the letter or number pointed to by the start pointer is the same as the one pointed to by the end pointer, after making sure they are both in the same case (like all lowercase).
If at any point the characters don't match, you know immediately that the phrase isn't a palindrome, and you can stop.
If the pointers meet or cross each other without finding any mismatches, then the entire phrase is a palindrome.

Code Implementation

def is_palindrome(input_string):
    left_pointer = 0
    right_pointer = len(input_string) - 1

    while left_pointer < right_pointer:
        # Advance left pointer past non-alphanumeric characters.
        if not input_string[left_pointer].isalnum():
            left_pointer += 1
            continue

        # Advance right pointer past non-alphanumeric characters.
        if not input_string[right_pointer].isalnum():
            right_pointer -= 1
            continue

        # Compare characters, ignoring case.
        if input_string[left_pointer].lower() != input_string[right_pointer].lower():
            return False

        # Move pointers towards the center.
        left_pointer += 1
        right_pointer -= 1

    # If pointers meet or cross without mismatches, it's a palindrome.
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string input	An empty string is considered a palindrome, so the function should return true.
String with only non-alphanumeric characters	After processing, the string becomes empty, which is a valid palindrome and should return true.
String with a single alphanumeric character	A single character string is always a palindrome, so the function should return true.
String with mixed case letters and numbers	All uppercase letters should be converted to lowercase, and only alphanumeric characters should be considered for the palindrome check.
String with all identical alphanumeric characters	Such strings are always palindromes, and the algorithm should correctly identify this.
Very long strings	The solution should be efficient in terms of time and space complexity to handle potentially large inputs without exceeding typical memory or time limits.
String with leading or trailing non-alphanumeric characters	These characters should be ignored during the processing and palindrome check.
String with unicode characters that are alphanumeric	Ensure the alphanumeric check correctly identifies and processes alphanumeric characters across different Unicode ranges if applicable, though standard ASCII is usually assumed.

Empty string input

How to Handle:

An empty string is considered a palindrome, so the function should return true.

String with only non-alphanumeric characters

How to Handle:

After processing, the string becomes empty, which is a valid palindrome and should return true.

String with a single alphanumeric character

How to Handle:

A single character string is always a palindrome, so the function should return true.

String with mixed case letters and numbers

How to Handle:

All uppercase letters should be converted to lowercase, and only alphanumeric characters should be considered for the palindrome check.

String with all identical alphanumeric characters

How to Handle:

Such strings are always palindromes, and the algorithm should correctly identify this.

Very long strings

How to Handle:

The solution should be efficient in terms of time and space complexity to handle potentially large inputs without exceeding typical memory or time limits.

String with leading or trailing non-alphanumeric characters

How to Handle:

These characters should be ignored during the processing and palindrome check.

String with unicode characters that are alphanumeric

How to Handle:

Ensure the alphanumeric check correctly identifies and processes alphanumeric characters across different Unicode ranges if applicable, though standard ASCII is usually assumed.

0/3 Bank of America questions completed

0/3 completed