Mirror Pair Indices

HardTries & Strings

Problem

Given a list of distinct strings words, find every ordered pair of different indices [i, j] such that words[i] + words[j] is a palindrome.

Return the pairs sorted ascending by i, then by j.

Example 1

Input:
words = ["ab","ba","abc","cba","a"]
Output:
[[0,1],[0,3],[0,4],[1,0],[2,1],[2,3],[3,2],[4,1]]

For example "ab" + "cba" = "abcba" and "a" + "ba" = "aba".

Example 2

Input:
words = ["a",""]
Output:
[[0,1],[1,0]]

The empty word joins any palindrome on either side.

Example 3

Input:
words = ["abc","xyz"]
Output:
[]

Constraints

  • 1 ≤ words.length ≤ 5000
  • 0 ≤ words[i].length ≤ 300
  • Lowercase English letters; words are distinct.

Hint

Show the first hint

Trying all n² pairs and checking each concatenation is too slow. Fix one word and ask what its partner must look like.

Walkthrough

How to approach it

01Clarify before coding

  • Ordered pairs? Yes: [i, j] and [j, i] are different, and both may be valid.
  • Can i equal j? No.
  • Can a word be empty? Yes; it pairs with every palindrome on both sides.

02Brute force

For every ordered pair, concatenate and test for a palindrome.

Cost: O(n²·k): 2.5·10^7 pairs times strings up to 600 characters long.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.