Find palindrome-forming string pairs
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.
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.