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.
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.