Jobs

Interviews

Discussions

Valid Palindrome IV

Medium

Amazon

3 views

Topics:

StringsTwo Pointers

You are given a string s. You can perform the following operation at most twice: You can swap any two characters in the string s. After performing this operation at most twice return true if you can make the given string a palindrome; otherwise, return false.

For example:

s = "abcba" Output: true (already a palindrome)
s = "abcca" Output: true (swap b and c to make accaa which can be converted to a palindrome by swapping the two cs)
s = "ababaa" Output: false (no two swaps can make this a palindrome)
s = "abbca" Output: true (swap b with the last a: abcba which is a palindrome)
s = "abcdefgh" Output: false

Can you provide an efficient algorithm to solve this problem? What is the time and space complexity of your solution? Consider edge cases such as empty or single-character strings.

Valid Palindrome IV

Medium

Amazon

3 views

Topics:

StringsTwo Pointers

For example:

s = "abcba" Output: true (already a palindrome)
s = "abcca" Output: true (swap b and c to make accaa which can be converted to a palindrome by swapping the two cs)
s = "ababaa" Output: false (no two swaps can make this a palindrome)
s = "abbca" Output: true (swap b with the last a: abcba which is a palindrome)
s = "abcdefgh" Output: false

Can you provide an efficient algorithm to solve this problem? What is the time and space complexity of your solution? Consider edge cases such as empty or single-character strings.

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 might the input string contain (e.g., only alphanumeric, or also punctuation and spaces)?
Is the comparison case-insensitive? Should I treat uppercase and lowercase letters as the same?
If the string is already a valid palindrome, is exactly one modification still required, or should I return false?
What constitutes a 'modification'? Can I insert, delete, or substitute characters, or am I limited to substitutions?
By 'valid palindrome', do you require that exactly *one* modification results in a palindrome, or is at least one sufficient?

Brute Force Solution

Approach

The brute force approach to this palindrome problem involves checking almost every possible way to make the string a palindrome. We consider flipping pairs of characters, one pair at a time, to see if the resulting string reads the same forward and backward. If we find at least one such pair, then the string can become a palindrome.

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

First, check if the original string is already a palindrome. If it is, we're done; the answer is yes.
If it's not, we need to start making changes.
Imagine picking two positions in the string. Swap the characters at those two positions.
Then, check if the new string is a palindrome. If it is, we've found a solution; the answer is yes.
If it's still not a palindrome, undo the swap. Put the characters back where they were.
Repeat the swap-and-check process for every possible pair of positions in the string.
If, after trying every possible pair of positions, you never found a palindrome, the answer is no; it is not possible to create a palindrome with only one swap.

Code Implementation

def valid_palindrome_iv_brute_force(input_string):
    # First, check if the original string is already a palindrome.
    if input_string == input_string[::-1]:
        return True

    string_length = len(input_string)

    for first_index in range(string_length):
        for second_index in range(first_index + 1, string_length):
            # Create a list of characters from the string to allow modification
            string_list = list(input_string)

            # Swap characters at the chosen indices
            string_list[first_index], string_list[second_index] = string_list[second_index], string_list[first_index]

            modified_string = "".join(string_list)

            # Check if the modified string is a palindrome
            if modified_string == modified_string[::-1]:
                return True

            # Swap the characters back to undo the modification
            string_list[first_index], string_list[second_index] = string_list[second_index], string_list[first_index]

    # If no palindrome is found after all swaps, return False
    return False

Big(O) Analysis

Time Complexity

O(n³) – The algorithm first checks if the original string is a palindrome, which takes O(n) time. If not, it iterates through all possible pairs of indices in the string, which requires nested loops. For each pair, it swaps the characters (O(1)), checks if the new string is a palindrome (O(n)), and then swaps back (O(1)). Thus, the pair checking takes O(n²) to iterate and for each iteration there is an O(n) palindrome check giving O(n³) in total. Therefore, the overall time complexity is dominated by the nested loops and palindrome check, resulting in O(n³).

Space Complexity

O(1) – The described brute force approach primarily involves swapping characters within the input string and checking for palindromes. It does not explicitly create or use any auxiliary data structures that scale with the input string's length, N. The operations use a fixed number of variables to store indices for swapping. Thus, the space complexity is constant, independent of the input string's size.

Optimal Solution

Approach

The key to efficiently checking if a slightly altered string can be a palindrome is to focus on the differences and where they are located. Instead of rebuilding or reversing the whole string, we smartly compare portions to avoid unnecessary work. This saves a significant amount of computation.

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

First, compare the string from the start to the end, character by character, to find the first difference.
Also, look from the end to the start to find the last difference.
If there are more than two differences, the string can't be made a palindrome with just one change, so it's false.
If there are zero differences, then the string is already a palindrome, so it is true.
If there's only one difference, that difference needs to be right in the middle so that changing it creates a palindrome, otherwise it's false.
If there are two differences, check if by making only one character change, the string becomes a palindrome. We can determine this by strategically comparing the characters around those two differences.
After checking, if the string is a palindrome it is true otherwise false.

Code Implementation

def is_valid_palindrome_iv(input_string):
    left_index = 0
    right_index = len(input_string) - 1
    first_difference = -1
    last_difference = -1

    while left_index < right_index:
        if input_string[left_index] != input_string[right_index]:
            if first_difference == -1:
                first_difference = left_index
            last_difference = right_index

        left_index += 1
        right_index -= 1

    if first_difference == -1:
        return True

    if first_difference == last_difference:
        return True

    if first_difference != -1 and last_difference != -1:
        # Need to handle two differences
        if (last_difference - first_difference) > 1:

            # If more than one index separates the differences
            if input_string[first_difference + 1] == input_string[last_difference]:
                first_difference_index = first_difference + 1
                last_difference_index = last_difference - 1
            elif input_string[first_difference] == input_string[last_difference - 1]:
                first_difference_index = first_difference + 1
                last_difference_index = last_difference - 1
            else:
                return False
        else:
            return True

        while first_difference_index < last_difference_index:
            if input_string[first_difference_index] != input_string[last_difference_index]:
                return False
            first_difference_index += 1
            last_difference_index -= 1

        return True
    return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the string from both ends towards the middle to find the first and last differences. In the worst case, this might involve comparing all characters in the string, resulting in a single pass. After locating the differences, a constant number of additional comparisons are made. Therefore, the dominant factor is the initial scan of the string which is linearly proportional to the string's length n. Thus, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It stores a few integer variables to track the indices of the first and last differences, but the number of such variables does not depend on the input string's length, N. No dynamic data structures like arrays, lists, or hash maps are created that scale with N. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty string input	Return true, as an empty string is considered a valid palindrome, or throw IllegalArgumentException, depending on problem requirement.
String with a single character	Return true, as a single character string is a valid palindrome.
String with two characters that are the same	Return true as it forms a palindrome after one operation.
String with two characters that are different	Return false as it cannot form a palindrome with one change.
String with all identical characters	Return true since the string is already a valid palindrome.
String that is already a valid palindrome	Return true since no modification is needed.
Very long string exceeding memory constraints	Consider in-place modification algorithms or algorithms with minimal memory overhead to avoid exceeding memory limits and causing runtime errors.
String with non-alphanumeric characters	Filter or skip non-alphanumeric characters during palindrome check, converting the input string to only consider alphanumeric portions.

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 might the input string contain (e.g., only alphanumeric, or also punctuation and spaces)?
Is the comparison case-insensitive? Should I treat uppercase and lowercase letters as the same?
If the string is already a valid palindrome, is exactly one modification still required, or should I return false?
What constitutes a 'modification'? Can I insert, delete, or substitute characters, or am I limited to substitutions?
By 'valid palindrome', do you require that exactly *one* modification results in a palindrome, or is at least one sufficient?

Brute Force Solution

Approach

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

First, check if the original string is already a palindrome. If it is, we're done; the answer is yes.
If it's not, we need to start making changes.
Imagine picking two positions in the string. Swap the characters at those two positions.
Then, check if the new string is a palindrome. If it is, we've found a solution; the answer is yes.
If it's still not a palindrome, undo the swap. Put the characters back where they were.
Repeat the swap-and-check process for every possible pair of positions in the string.
If, after trying every possible pair of positions, you never found a palindrome, the answer is no; it is not possible to create a palindrome with only one swap.

Code Implementation

def valid_palindrome_iv_brute_force(input_string):
    # First, check if the original string is already a palindrome.
    if input_string == input_string[::-1]:
        return True

    string_length = len(input_string)

    for first_index in range(string_length):
        for second_index in range(first_index + 1, string_length):
            # Create a list of characters from the string to allow modification
            string_list = list(input_string)

            # Swap characters at the chosen indices
            string_list[first_index], string_list[second_index] = string_list[second_index], string_list[first_index]

            modified_string = "".join(string_list)

            # Check if the modified string is a palindrome
            if modified_string == modified_string[::-1]:
                return True

            # Swap the characters back to undo the modification
            string_list[first_index], string_list[second_index] = string_list[second_index], string_list[first_index]

    # If no palindrome is found after all swaps, return False
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, compare the string from the start to the end, character by character, to find the first difference.
Also, look from the end to the start to find the last difference.
If there are more than two differences, the string can't be made a palindrome with just one change, so it's false.
If there are zero differences, then the string is already a palindrome, so it is true.
If there's only one difference, that difference needs to be right in the middle so that changing it creates a palindrome, otherwise it's false.
If there are two differences, check if by making only one character change, the string becomes a palindrome. We can determine this by strategically comparing the characters around those two differences.
After checking, if the string is a palindrome it is true otherwise false.

Code Implementation

def is_valid_palindrome_iv(input_string):
    left_index = 0
    right_index = len(input_string) - 1
    first_difference = -1
    last_difference = -1

    while left_index < right_index:
        if input_string[left_index] != input_string[right_index]:
            if first_difference == -1:
                first_difference = left_index
            last_difference = right_index

        left_index += 1
        right_index -= 1

    if first_difference == -1:
        return True

    if first_difference == last_difference:
        return True

    if first_difference != -1 and last_difference != -1:
        # Need to handle two differences
        if (last_difference - first_difference) > 1:

            # If more than one index separates the differences
            if input_string[first_difference + 1] == input_string[last_difference]:
                first_difference_index = first_difference + 1
                last_difference_index = last_difference - 1
            elif input_string[first_difference] == input_string[last_difference - 1]:
                first_difference_index = first_difference + 1
                last_difference_index = last_difference - 1
            else:
                return False
        else:
            return True

        while first_difference_index < last_difference_index:
            if input_string[first_difference_index] != input_string[last_difference_index]:
                return False
            first_difference_index += 1
            last_difference_index -= 1

        return True
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return true, as an empty string is considered a valid palindrome, or throw IllegalArgumentException, depending on problem requirement.
String with a single character	Return true, as a single character string is a valid palindrome.
String with two characters that are the same	Return true as it forms a palindrome after one operation.
String with two characters that are different	Return false as it cannot form a palindrome with one change.
String with all identical characters	Return true since the string is already a valid palindrome.
String that is already a valid palindrome	Return true since no modification is needed.
Very long string exceeding memory constraints	Consider in-place modification algorithms or algorithms with minimal memory overhead to avoid exceeding memory limits and causing runtime errors.
String with non-alphanumeric characters	Filter or skip non-alphanumeric characters during palindrome check, converting the input string to only consider alphanumeric portions.