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.

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.