Jobs

Interviews

Discussions

Valid Palindrome II

Easy

Google

1 view

Topics:

StringsTwo Pointers

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters.

Valid Palindrome II

Easy

Google

1 view

Topics:

StringsTwo Pointers

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters.

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 maximum length of the input string 's'?
Can the input string 's' contain non-alphanumeric characters (e.g., spaces, punctuation)? If so, should I ignore them for the palindrome check?
Is the comparison case-sensitive, or should I treat uppercase and lowercase letters as equal?
If the string is already a palindrome, should I return true?
If there are multiple characters that can be removed to make the string a palindrome, can I remove any one of them?

Brute Force Solution

Approach

The brute force approach for this problem is to consider every possible string that could be formed by removing one character. We simply check each of these strings to see if they are palindromes. If we find a palindrome, we have our answer.

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

Start with the original string.
Try removing the first character and check if the remaining string is a palindrome.
If it is, we're done. If not, put the character back.
Now, try removing the second character and check if the remaining string is a palindrome.
If it is, we're done. If not, put the character back.
Keep doing this for every character in the original string: remove it, check for a palindrome, and if it's not a palindrome, put the character back.
Also, check if the original string, without removing any characters, is already a palindrome.
If you find any of these resulting strings to be a palindrome at any step, then the answer is yes, the original string is a valid palindrome with one removal allowed.
If after checking all possible removals and the original string itself, you haven't found a palindrome, then the answer is no.

Code Implementation

def valid_palindrome_two(input_string):
    string_length = len(input_string)

    def is_palindrome(substring):
        left_pointer = 0
        right_pointer = len(substring) - 1
        while left_pointer < right_pointer:
            if substring[left_pointer] != substring[right_pointer]:
                return False
            left_pointer += 1
            right_pointer -= 1
        return True

    # First, check if the original string is a palindrome
    if is_palindrome(input_string):
        return True

    for index_to_remove in range(string_length):
        # Create a new string with one character removed
        modified_string = input_string[:index_to_remove] + input_string[index_to_remove+1:]

        # Check if the modified string is a palindrome
        # If it is, we've found a valid palindrome with one removal
        if is_palindrome(modified_string):
            return True

    # If none of the removals resulted in a palindrome,
    # then the original string cannot be made a palindrome
    return False

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n characters in the string. For each character, it creates a substring by removing that character, which takes O(n) time. Then, it checks if the substring is a palindrome, which also takes O(n) time in the worst case. Since we perform these operations for each of the n characters, the overall time complexity is approximately n * n, leading to O(n²).

Space Complexity

O(N) – The brute force approach creates substrings by removing characters. In the worst case, checking each removal involves creating a copy of almost the entire string, resulting in a new string of length N-1, where N is the length of the original string. The 'is a palindrome' check also potentially uses a substring of length N. Therefore, the auxiliary space used depends linearly on the input string's length, N. This leads to a space complexity of O(N).

Optimal Solution

Approach

The fast way to check if a string can become a palindrome by removing at most one character is to compare the string from both ends. If we find a mismatch, we'll check if the string is a palindrome by skipping one character from the left or from the right.

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

Start by comparing the characters from the very beginning and the very end of the string, moving inwards.
If the characters match, continue moving towards the middle.
If you find characters that don't match, this is where it gets interesting.
Now, imagine you remove the character on the left side that caused the mismatch and check if the remaining string is a palindrome.
Next, imagine you remove the character on the right side instead and check if *that* remaining string is a palindrome.
If either of those strings (removing either the left or the right character) is a palindrome, then the original string can be made a palindrome by removing just one character.
If neither removing the left nor the right character creates a palindrome, then the original string cannot be made a palindrome by removing one character.

Code Implementation

def validPalindrome(input_string: str) -> bool:

    def isPalindrome(input_string: str, start_index: int, end_index: int) -> bool:
        while start_index < end_index:
            if input_string[start_index] != input_string[end_index]:
                return False
            start_index += 1
            end_index -= 1
        return True

    start_index = 0
    end_index = len(input_string) - 1

    while start_index < end_index:
        if input_string[start_index] != input_string[end_index]:
            # Mismatch found; check both removal options.

            #Check by removing the character at start_index.
            is_palindrome_skipping_start = isPalindrome(input_string, start_index + 1, end_index)

            #Check by removing the character at end_index.
            is_palindrome_skipping_end = isPalindrome(input_string, start_index, end_index - 1)

            #If either is a palindrome, return True.
            return is_palindrome_skipping_start or is_palindrome_skipping_end

        start_index += 1
        end_index -= 1

    #If no mismatches, it's already a palindrome.
    return True

Big(O) Analysis

Time Complexity

O(n) – The primary operation involves traversing the string from both ends towards the middle, which takes O(n) time in the worst case. If a mismatch is found, we invoke a helper function to check if the substring formed by removing either the left or right character is a palindrome. Each of these palindrome checks also takes O(n) time. However, these palindrome checks occur at most twice. Therefore, the overall time complexity remains O(n) because 2*O(n) simplifies to O(n).

Space Complexity

O(1) – The provided solution uses a constant amount of extra space. It primarily involves comparing characters using two pointers, and when a mismatch is found, it explores two sub-strings. The sub-string checks, however, don't create new copies of the strings. Instead, they operate on the original string using different start and end indices. Therefore, regardless of the input string's length N, the algorithm only requires a few integer variables to track indices, resulting in constant space complexity.

Edge Cases

Case	How to Handle
Null or empty string	Return true; an empty string is considered a palindrome.
String of length 1	Return true; a single-character string is a palindrome.
String of length 2, palindrome	Return true; it's already a palindrome without deletion.
String of length 2, not a palindrome	Return true; removing either character makes it a palindrome.
Very long string	Ensure the solution has O(n) time complexity (e.g., two-pointer approach) to avoid timeouts.
String that is already a palindrome	Return true; no deletion is needed.
String with mixed case letters (e.g., 'Racecar')	Convert the string to lowercase or uppercase before checking for palindrome properties.
String with non-alphanumeric characters (e.g., 'A man, a plan, a canal: Panama')	Filter out non-alphanumeric characters before checking for palindrome properties; alternatively, adjust the palindrome check to only consider alphanumeric 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 is the maximum length of the input string 's'?
Can the input string 's' contain non-alphanumeric characters (e.g., spaces, punctuation)? If so, should I ignore them for the palindrome check?
Is the comparison case-sensitive, or should I treat uppercase and lowercase letters as equal?
If the string is already a palindrome, should I return true?
If there are multiple characters that can be removed to make the string a palindrome, can I remove any one of them?

Brute Force Solution

Approach

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

Start with the original string.
Try removing the first character and check if the remaining string is a palindrome.
If it is, we're done. If not, put the character back.
Now, try removing the second character and check if the remaining string is a palindrome.
If it is, we're done. If not, put the character back.
Keep doing this for every character in the original string: remove it, check for a palindrome, and if it's not a palindrome, put the character back.
Also, check if the original string, without removing any characters, is already a palindrome.
If you find any of these resulting strings to be a palindrome at any step, then the answer is yes, the original string is a valid palindrome with one removal allowed.
If after checking all possible removals and the original string itself, you haven't found a palindrome, then the answer is no.

Code Implementation

def valid_palindrome_two(input_string):
    string_length = len(input_string)

    def is_palindrome(substring):
        left_pointer = 0
        right_pointer = len(substring) - 1
        while left_pointer < right_pointer:
            if substring[left_pointer] != substring[right_pointer]:
                return False
            left_pointer += 1
            right_pointer -= 1
        return True

    # First, check if the original string is a palindrome
    if is_palindrome(input_string):
        return True

    for index_to_remove in range(string_length):
        # Create a new string with one character removed
        modified_string = input_string[:index_to_remove] + input_string[index_to_remove+1:]

        # Check if the modified string is a palindrome
        # If it is, we've found a valid palindrome with one removal
        if is_palindrome(modified_string):
            return True

    # If none of the removals resulted in a palindrome,
    # then the original string cannot be made a palindrome
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start by comparing the characters from the very beginning and the very end of the string, moving inwards.
If the characters match, continue moving towards the middle.
If you find characters that don't match, this is where it gets interesting.
Now, imagine you remove the character on the left side that caused the mismatch and check if the remaining string is a palindrome.
Next, imagine you remove the character on the right side instead and check if *that* remaining string is a palindrome.
If either of those strings (removing either the left or the right character) is a palindrome, then the original string can be made a palindrome by removing just one character.
If neither removing the left nor the right character creates a palindrome, then the original string cannot be made a palindrome by removing one character.

Code Implementation

def validPalindrome(input_string: str) -> bool:

    def isPalindrome(input_string: str, start_index: int, end_index: int) -> bool:
        while start_index < end_index:
            if input_string[start_index] != input_string[end_index]:
                return False
            start_index += 1
            end_index -= 1
        return True

    start_index = 0
    end_index = len(input_string) - 1

    while start_index < end_index:
        if input_string[start_index] != input_string[end_index]:
            # Mismatch found; check both removal options.

            #Check by removing the character at start_index.
            is_palindrome_skipping_start = isPalindrome(input_string, start_index + 1, end_index)

            #Check by removing the character at end_index.
            is_palindrome_skipping_end = isPalindrome(input_string, start_index, end_index - 1)

            #If either is a palindrome, return True.
            return is_palindrome_skipping_start or is_palindrome_skipping_end

        start_index += 1
        end_index -= 1

    #If no mismatches, it's already a palindrome.
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string	Return true; an empty string is considered a palindrome.
String of length 1	Return true; a single-character string is a palindrome.
String of length 2, palindrome	Return true; it's already a palindrome without deletion.
String of length 2, not a palindrome	Return true; removing either character makes it a palindrome.
Very long string	Ensure the solution has O(n) time complexity (e.g., two-pointer approach) to avoid timeouts.
String that is already a palindrome	Return true; no deletion is needed.
String with mixed case letters (e.g., 'Racecar')	Convert the string to lowercase or uppercase before checking for palindrome properties.
String with non-alphanumeric characters (e.g., 'A man, a plan, a canal: Panama')	Filter out non-alphanumeric characters before checking for palindrome properties; alternatively, adjust the palindrome check to only consider alphanumeric characters.