Jobs

Interviews

Discussions

Palindrome Pairs

Hard

Google

2 views

Topics:

ArraysStringsTwo Pointers

You are given a 0-indexed array of unique strings words.

A palindrome pair is a pair of integers (i, j) such that:

0 <= i, j < words.length,
i != j, and
words[i] + words[j] (the concatenation of the two strings) is a palindrome.

Return an array of all the palindrome pairs of words.

You must write an algorithm with O(sum of words[i].length) runtime complexity.

For example:

words = ["abcd","dcba","lls","s","sssll"] should return [[0,1],[1,0],[3,2],[2,4]] because the palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]
words = ["bat","tab","cat"] should return [[0,1],[1,0]] because the palindromes are ["battab","tabbat"]
words = ["a",""] should return [[0,1],[1,0]] because the palindromes are ["a","a"]

Palindrome Pairs

Hard

Google

2 views

Topics:

ArraysStringsTwo Pointers

You are given a 0-indexed array of unique strings words.

A palindrome pair is a pair of integers (i, j) such that:

0 <= i, j < words.length,
i != j, and
words[i] + words[j] (the concatenation of the two strings) is a palindrome.

Return an array of all the palindrome pairs of words.

You must write an algorithm with O(sum of words[i].length) runtime complexity.

For example:

words = ["abcd","dcba","lls","s","sssll"] should return [[0,1],[1,0],[3,2],[2,4]] because the palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]
words = ["bat","tab","cat"] should return [[0,1],[1,0]] because the palindromes are ["battab","tabbat"]
words = ["a",""] should return [[0,1],[1,0]] because the palindromes are ["a","a"]

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:

Can the input list of words contain empty strings or null values?
What is the maximum length of each word in the input list?
If multiple palindrome pairs exist, can I return any one of them, or is there a specific order or preference?
Does a word paired with itself (at different indices) count as a palindrome pair if their concatenation forms a palindrome?
If no palindrome pairs exist, what should I return (e.g., an empty list, null, or a specific error code)?

Brute Force Solution

Approach

The goal is to find pairs of words that, when combined, form a palindrome (reads the same forwards and backward). The brute force method explores every possible combination of words to see if they create a palindrome when joined together.

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

Take the first word in the list.
For that first word, go through every other word in the list, one at a time.
Combine the first word with each of the other words to create a new combined word.
Check if the combined word is a palindrome (reads the same forward and backward).
If it is a palindrome, we've found a pair and save it.
Repeat these steps, but switch the order of the words, combining the second word with the first, to see if that's a palindrome too.
After checking the first word against all the others, move to the second word in the original list and repeat the entire process.
Continue until you've checked every single word against every other word.

Code Implementation

def palindrome_pairs_brute_force(words):
    result = []

    for first_word_index in range(len(words)):
        for second_word_index in range(len(words)):
            # Avoid comparing a word with itself
            if first_word_index == second_word_index:
                continue

            combined_word = words[first_word_index] + words[second_word_index]

            # Check if the combined word is a palindrome
            if combined_word == combined_word[::-1]:

                result.append([first_word_index, second_word_index])

    return result

Big(O) Analysis

Time Complexity

O(n² * k) – The algorithm iterates through each of the n words in the input list. Inside the outer loop, another loop iterates through the remaining n words. For each pair of words, a concatenation happens taking O(k) time where k is the average length of the strings. Finally the palindrome check takes O(k) time where k is the average length of the string. Therefore the total runtime can be approximated as n * n * k or O(n² * k).

Space Complexity

O(1) – The provided brute force algorithm primarily iterates through the input list. It combines words and checks for palindromes directly without creating any significant auxiliary data structures that scale with the input size. Although temporary string variables are created during combination and palindrome checking, their sizes are bounded by the length of the input words, not the number of words N. Therefore, the extra space used remains constant, regardless of the number of words in the input list, making it O(1).

Optimal Solution

Approach

The problem is to find pairs of words that when combined, form a palindrome. Instead of checking every possible combination of words, we can be much more efficient. The key is to use a data structure that helps us quickly find potential palindrome matches by looking at reversed versions of the words.

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

First, store all the words in a special structure that lets us quickly look up reversed words.
Then, for each word, consider two main possibilities: the word comes first in the combined pair, or it comes second.
If the word comes first, check if the rest of the combined word (after the first word) needs to be a palindrome.
If the word comes second, check if the beginning part of the combined word (before the second word) needs to be a palindrome.
The fast lookup structure will quickly tell us if there's a word in our list that satisfies the 'rest of the combined word' or 'beginning part of the combined word' palindrome requirements.
If such a word exists, we have found a palindrome pair! Repeat for all words in the input.

Code Implementation

def palindrome_pairs(words):
    word_to_index = {word: index for index, word in enumerate(words)}
    results = []

    for index, word in enumerate(words):
        for j in range(len(word) + 1):
            # Consider cases where word is on the left.
            prefix = word[:j]
            suffix = word[j:]

            if is_palindrome(prefix):
                reversed_suffix = suffix[::-1]

                if reversed_suffix in word_to_index and word_to_index[reversed_suffix] != index:
                    results.append((word_to_index[reversed_suffix], index))

            # Consider cases where word is on the right.
            prefix = word[:j]
            suffix = word[j:]

            if is_palindrome(suffix) and suffix != "":
                reversed_prefix = prefix[::-1]
                # To avoid duplicates, check non-empty suffix
                if reversed_prefix in word_to_index and word_to_index[reversed_prefix] != index:
                    results.append((index, word_to_index[reversed_prefix]))

    return results

def is_palindrome(word):
    left = 0
    right = len(word) - 1

    # Check if a given string is a palindrome.
    while left < right:
        if word[left] != word[right]:
            return False
        left += 1
        right -= 1

    return True

Big(O) Analysis

Time Complexity

O(n * (k^2 + m)) – Let n be the number of words in the input, k be the average length of a word, and m be the average number of potential palindrome pairs found for a given word. The initial storage and lookup structure construction (e.g., using a Trie or HashMap) takes O(n*k) time to insert all the words and their reversed forms. Then, for each of the n words, we iterate through all possible prefixes and suffixes to check for palindrome conditions which involves string slicing or substring operations costing O(k). Checking if those prefixes or suffixes are palindromes is O(k). Searching for the matching reversed words using the lookup is O(k). Overall, checking one word for potential matches will then be O(k * (k+k)). Since there can be multiple palindrome pairs we can discover per string we must check for palindrome substring which is O(k^2) plus the time to append to our results. We repeat this for n elements giving us O(n * (k^2 + m))

Space Complexity

O(NW) – The space complexity is dominated by the storage of reversed words in the fast lookup structure, presumably a hash map or trie. In the worst case, we store all N words, and each word can have a maximum length of W. Therefore, the space required to store all the reversed words is proportional to the total number of characters in all the words, which is NW. Consequently, the auxiliary space complexity is O(NW), where N is the number of words and W is the maximum length of a word.

Edge Cases

Case	How to Handle
Input array is null or empty	Return an empty list to indicate no palindrome pairs can be formed.
Array contains an empty string	The empty string can form a palindrome pair with any palindrome string in the array; must check all other strings against the empty string.
Array contains only one string	Return an empty list, since a pair requires at least two strings.
Two identical strings in the array	The identical strings form a palindrome pair (string1 + string2, string2 + string1).
Maximum string length or large number of strings leading to timeout	Optimize the palindrome check to avoid redundant computations, possibly using dynamic programming or a precomputed table.
Strings that are palindromes themselves	These strings will form pairs with an empty string (if present) or their own reverse.
Strings with very long common prefixes or suffixes	Consider optimizations like using a Trie data structure to efficiently search for prefixes/suffixes that form palindromes.
Input array contains very long strings that could lead to memory issues	Implement a streaming approach or limit the length of strings processed to stay within memory constraints.

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:

Can the input list of words contain empty strings or null values?
What is the maximum length of each word in the input list?
If multiple palindrome pairs exist, can I return any one of them, or is there a specific order or preference?
Does a word paired with itself (at different indices) count as a palindrome pair if their concatenation forms a palindrome?
If no palindrome pairs exist, what should I return (e.g., an empty list, null, or a specific error code)?

Brute Force Solution

Approach

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

Take the first word in the list.
For that first word, go through every other word in the list, one at a time.
Combine the first word with each of the other words to create a new combined word.
Check if the combined word is a palindrome (reads the same forward and backward).
If it is a palindrome, we've found a pair and save it.
Repeat these steps, but switch the order of the words, combining the second word with the first, to see if that's a palindrome too.
After checking the first word against all the others, move to the second word in the original list and repeat the entire process.
Continue until you've checked every single word against every other word.

Code Implementation

def palindrome_pairs_brute_force(words):
    result = []

    for first_word_index in range(len(words)):
        for second_word_index in range(len(words)):
            # Avoid comparing a word with itself
            if first_word_index == second_word_index:
                continue

            combined_word = words[first_word_index] + words[second_word_index]

            # Check if the combined word is a palindrome
            if combined_word == combined_word[::-1]:

                result.append([first_word_index, second_word_index])

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, store all the words in a special structure that lets us quickly look up reversed words.
Then, for each word, consider two main possibilities: the word comes first in the combined pair, or it comes second.
If the word comes first, check if the rest of the combined word (after the first word) needs to be a palindrome.
If the word comes second, check if the beginning part of the combined word (before the second word) needs to be a palindrome.
The fast lookup structure will quickly tell us if there's a word in our list that satisfies the 'rest of the combined word' or 'beginning part of the combined word' palindrome requirements.
If such a word exists, we have found a palindrome pair! Repeat for all words in the input.

Code Implementation

def palindrome_pairs(words):
    word_to_index = {word: index for index, word in enumerate(words)}
    results = []

    for index, word in enumerate(words):
        for j in range(len(word) + 1):
            # Consider cases where word is on the left.
            prefix = word[:j]
            suffix = word[j:]

            if is_palindrome(prefix):
                reversed_suffix = suffix[::-1]

                if reversed_suffix in word_to_index and word_to_index[reversed_suffix] != index:
                    results.append((word_to_index[reversed_suffix], index))

            # Consider cases where word is on the right.
            prefix = word[:j]
            suffix = word[j:]

            if is_palindrome(suffix) and suffix != "":
                reversed_prefix = prefix[::-1]
                # To avoid duplicates, check non-empty suffix
                if reversed_prefix in word_to_index and word_to_index[reversed_prefix] != index:
                    results.append((index, word_to_index[reversed_prefix]))

    return results

def is_palindrome(word):
    left = 0
    right = len(word) - 1

    # Check if a given string is a palindrome.
    while left < right:
        if word[left] != word[right]:
            return False
        left += 1
        right -= 1

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input array is null or empty	Return an empty list to indicate no palindrome pairs can be formed.
Array contains an empty string	The empty string can form a palindrome pair with any palindrome string in the array; must check all other strings against the empty string.
Array contains only one string	Return an empty list, since a pair requires at least two strings.
Two identical strings in the array	The identical strings form a palindrome pair (string1 + string2, string2 + string1).
Maximum string length or large number of strings leading to timeout	Optimize the palindrome check to avoid redundant computations, possibly using dynamic programming or a precomputed table.
Strings that are palindromes themselves	These strings will form pairs with an empty string (if present) or their own reverse.
Strings with very long common prefixes or suffixes	Consider optimizations like using a Trie data structure to efficiently search for prefixes/suffixes that form palindromes.
Input array contains very long strings that could lead to memory issues	Implement a streaming approach or limit the length of strings processed to stay within memory constraints.