How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Airbnb.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Airbnb during technical interviews.

Find palindrome-forming string pairs | Airbnb Coding Question

Find palindrome-forming string pairs

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given an array of distinct lowercase strings words, return all index pairs (i, j) with i != j such that the concatenation words[i] + words[j] is a palindrome. Optimize for up to 100,000 words with total character count up to 200,000. Design an algorithm faster than the naive O(n^2 · L) approach, describing the data structures you would use (e.g., reversed-word trie, hash maps, palindromic prefix/suffix checks), how you would handle edge cases (empty string, single-character strings), and how you would avoid duplicate pairs. Analyze time and space complexity and provide test cases.

Quick Answer: This question evaluates string-processing and algorithmic design skills, including knowledge of efficient lookup data structures, palindrome properties, handling of edge cases, and time/space complexity analysis.

Given an array of distinct lowercase strings words, return all ordered index pairs [i, j] such that i != j and words[i] + words[j] is a palindrome. Return each valid pair exactly once, sorted by i and then j. The intended solution should be faster than the naive O(n^2 * L) approach and must correctly handle cases such as the empty string and single-character words.

Constraints

0 <= len(words) <= 100000
All words are distinct and contain only lowercase English letters
0 <= len(words[i])
The sum of all string lengths is at most 200000

Examples

Input: (["bat", "tab", "cat"],)

Expected Output: [[0, 1], [1, 0]]

Explanation: "bat" + "tab" and "tab" + "bat" are palindromes; no pair involving "cat" works.

Input: (["abcd", "dcba", "lls", "s", "sssll"],)

Expected Output: [[0, 1], [1, 0], [2, 4], [3, 2]]

Explanation: The reverse-word pairs are [0,1] and [1,0]. Also, "lls" + "sssll" = "llssssll" and "s" + "lls" = "slls", both palindromes.

Input: (["", "aba", "xyz", "a"],)

Expected Output: [[0, 1], [0, 3], [1, 0], [3, 0]]

Explanation: The empty string can pair on either side with any palindrome, so it matches "aba" and "a".

Input: (["a", "ba", "ab", ""],)

Expected Output: [[0, 1], [0, 3], [1, 2], [2, 0], [2, 1], [3, 0]]

Explanation: "a" + "ba" = "aba", "ba" + "ab" = "baab", "ab" + "a" = "aba", "ab" + "ba" = "abba", and the empty string pairs with the palindrome "a".

Input: ([],)

Expected Output: []

Explanation: With no words, there are no pairs.

Input: (["abc", "def"],)

Expected Output: []

Explanation: Neither concatenation forms a palindrome, so the answer is empty.

Solution

def solution(words):
    class TrieNode:
        __slots__ = ('children', 'word_index', 'pal_list')

        def __init__(self):
            self.children = {}
            self.word_index = -1
            self.pal_list = []

    def manacher_prefix_suffix(s):
        n = len(s)
        prefix = [False] * (n + 1)
        suffix = [False] * (n + 1)
        prefix[0] = True
        suffix[n] = True

        d1 = [0] * n
        l = 0
        r = -1
        for i in range(n):
            k = 1 if i > r else min(d1[l + r - i], r - i + 1)
            while i - k >= 0 and i + k < n and s[i - k] == s[i + k]:
                k += 1
            d1[i] = k
            if i + k - 1 > r:
                l = i - k + 1
                r = i + k - 1

        d2 = [0] * n
        l = 0
        r = -1
        for i in range(n):
            k = 0 if i > r else min(d2[l + r - i + 1], r - i + 1)
            while i - k - 1 >= 0 and i + k < n and s[i - k - 1] == s[i + k]:
                k += 1
            d2[i] = k
            if i + k - 1 > r:
                l = i - k
                r = i + k - 1

        for i, rad in enumerate(d1):
            if rad >= i + 1:
                prefix[2 * i + 1] = True
            if rad >= n - i:
                suffix[2 * i - n + 1] = True

        for i, rad in enumerate(d2):
            if rad >= i:
                prefix[2 * i] = True
            if rad >= n - i:
                suffix[2 * i - n] = True

        return prefix, suffix

    root = TrieNode()

    for idx, word in enumerate(words):
        prefix, _ = manacher_prefix_suffix(word)
        node = root
        for j in range(len(word) - 1, -1, -1):
            if prefix[j + 1]:
                node.pal_list.append(idx)
            ch = word[j]
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.word_index = idx
        node.pal_list.append(idx)

    result = []
    seen = set()

    for i, word in enumerate(words):
        _, suffix = manacher_prefix_suffix(word)
        node = root
        matched = True

        for j, ch in enumerate(word):
            if node.word_index != -1 and node.word_index != i and suffix[j]:
                pair = (i, node.word_index)
                if pair not in seen:
                    seen.add(pair)
                    result.append([i, node.word_index])

            node = node.children.get(ch)
            if node is None:
                matched = False
                break

        if not matched:
            continue

        for j in node.pal_list:
            if j != i:
                pair = (i, j)
                if pair not in seen:
                    seen.add(pair)
                    result.append([i, j])

    result.sort()
    return result

Time complexity: O(C + P log P), where C is the total number of characters across all words and P is the number of returned pairs. Space complexity: O(C + P).

Hints

Comparing every pair is too slow. Try indexing reversed words so that matching candidates can be found while scanning a word character by character.
A trie of reversed words works well if each node also remembers which words have a palindromic remaining prefix. Precompute palindromic prefixes and suffixes in linear time per word.

Quick Overview

This question evaluates string-processing and algorithmic design skills, including knowledge of efficient lookup data structures, palindrome properties, handling of edge cases, and time/space complexity analysis.