We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Palindrome Pairs

Number: 336

Difficulty: Hard

Paid? No

Companies: Airbnb, Amazon, Goldman Sachs, Google, Yandex, Wix

Problem Description

Given an array of unique strings, find all pairs of indices (i, j) such that the concatenation of words[i] and words[j] forms a palindrome. The algorithm must work in O(sum of words[i].length) time.

Key Insights

  • A palindrome is a string that reads the same forwards and backwards.
  • For any given word, if you split it into two parts, one part (either prefix or suffix) might be a palindrome.
  • If the other part’s reverse exists elsewhere in the array, then that reverse can be concatenated to yield a palindrome.
  • Carefully handle edge cases like empty strings, since an empty string is a palindrome by default.

Space and Time Complexity

Time Complexity: O(n * k^2) in the worst case where n is the number of words and k is the maximum word length, but with the palindrome checking optimized this can be considered O(sum of word lengths): Each word is processed once and each split is checked in O(k) time. Space Complexity: O(n * k) due to the hashmap storing all words and their indices.

Solution

We use a hashmap (dictionary) to store each word and its corresponding index. For every word, we iterate through every possible split position to divide the word into a prefix and a suffix. For each split:

  • If the prefix is a palindrome, we look for the reverse of the suffix in the hashmap. If found (and not the same word), then combining the reverse with the current word forms a palindrome.
  • Similarly, if the suffix is a palindrome, we look for the reverse of the prefix.

We must be cautious with edge cases, especially when either part is empty, as the empty string is considered a palindrome. This method avoids checking every possible pair explicitly and leverages string reversal and palindrome checks to achieve efficiency.

Code Solutions

# Python implementation for Palindrome Pairs

def is_palindrome(s):
    # Helper function to check if a string is a palindrome
    return s == s[::-1]

def palindromePairs(words):
    result = []
    # Create a dictionary mapping each word to its index
    word_dict = {word: i for i, word in enumerate(words)}
    
    # Iterate over each word with its index
    for i, word in enumerate(words):
        # For each possible split position (including edge empty string splits)
        for j in range(len(word) + 1):
            prefix = word[:j]
            suffix = word[j:]
            
            # If prefix is palindrome, check for reversed suffix in dictionary
            if is_palindrome(prefix):
                reversed_suffix = suffix[::-1]
                # Ensure that the reversed_suffix exists and is not the same word
                if reversed_suffix in word_dict and word_dict[reversed_suffix] != i:
                    result.append([word_dict[reversed_suffix], i])
            
            # Check the suffix; avoid duplicate pairs when j equals len(word) because
            # the case when suffix is empty was handled in the first condition
            if j != len(word) and is_palindrome(suffix):
                reversed_prefix = prefix[::-1]
                if reversed_prefix in word_dict and word_dict[reversed_prefix] != i:
                    result.append([i, word_dict[reversed_prefix]])
    
    return result

# Example Usage:
words = ["abcd", "dcba", "lls", "s", "sssll"]
print(palindromePairs(words))  # Expected Output: [[0,1],[1,0],[3,2],[2,4]]
← Back to All Questions