The O(n) Club: Palindrome Pairs — Hashmaps, Not Hunches

The O(n) Club: Palindrome Pairs — Hashmaps, Not Hunches

⚡ TL;DR

Find every unique pair of indices (i, j) in an array of words where words[i] + words[j] forms a palindrome. Yes, brute force solves it, but so did dial-up. Here’s how the slowpokes start:

// Please don’t do this — it’s O(N^2*K) torture
for (int i = 0; i < words.length; i++) {
  for (int j = 0; j < words.length; j++) {
    if (i != j && isPalindrome(words[i] + words[j])) {
      result.add(Arrays.asList(i, j));
    }
  }
}

🧠 How Devs Usually Mess This Up

You think finding palindrome pairs is just reversing words — "abc" + "cba", done. But plot twist: overlap is everything. “ab” + “ba”? Yep, that counts too. Most forget that empty strings pair with any palindrome like the world’s friendliest wildcard. And if you’re letting a word date itself, well… congrats on discovering bugs faster than features.

🔍 What’s Actually Going On

Imagine each word as a block of Jenga. You split it into every possible prefix/suffix — for each cut, you check if one part is a palindrome and if the reverse of the other part exists in the word dictionary (hashmap, preferably, because we’re not masochists). For every valid split, you get a new palindrome pair without all the unnecessary quadratic suffering.

🛠️ PseudoCode

• Build a HashMap mapping each word to its index for instant “find reverse” lookups.
• For each word w at index i:
  • Loop k = 0 to w.length (yes, including 0 and w.length):
  • Let prefix = w.substring(0, k), suffix = w.substring(k).
  • If prefix is a palindrome:
    • Is reverse(suffix) in the map and not i? Add [map.get(reverse(suffix)), i]
  • If suffix is a palindrome and k != w.length:
    • Is reverse(prefix) in the map and not i? Add [i, map.get(reverse(prefix))]
• Skip self-pairings, avoid duplicate/mirrored results unless both orders are palindromic.

💻 The Code

public List<List<Integer>> palindromePairs(String[] words) {
    List<List<Integer>> result = new ArrayList<>();
    Map<String, Integer> wordToIndex = new HashMap<>();
    for (int i = 0; i < words.length; i++) {
        wordToIndex.put(words[i], i);
    }
    for (int i = 0; i < words.length; i++) {
        String word = words[i];
        for (int k = 0; k <= word.length(); k++) {
            String prefix = word.substring(0, k);
            String suffix = word.substring(k);
            if (isPalindrome(prefix)) {
                String reversedSuffix = new StringBuilder(suffix).reverse().toString();
                Integer j = wordToIndex.get(reversedSuffix);
                if (j != null && j != i && reversedSuffix.length() != 0) {
                    result.add(Arrays.asList(j, i));
                }
            }
            if (k != word.length() && isPalindrome(suffix)) {
                String reversedPrefix = new StringBuilder(prefix).reverse().toString();
                Integer j = wordToIndex.get(reversedPrefix);
                if (j != null && j != i) {
                    result.add(Arrays.asList(i, j));
                }
            }
        }
    }
    return result;
}
 private boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left++) != s.charAt(right--)) return false;
    }
    return true;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Empty string is sneaky: It pairs with any palindrome (on either side). Don’t skip.
• Self-pairing? Nope. You can’t use the same word twice for a pair.
• Substring off-by-ones: Java will hand out exceptions like candy if you mis-split your word.
• Dupes: Don’t double-count [i, j] and [j, i] unless they’re both genuinely distinct palindromes.
• Complexity check: Time: O(N * K^2), Space: O(N * K). Tries? Not worth the existential crisis.

🧠 Interviewer Brain-Tattoo

“Palindromes aren’t just mirrors—they’re puzzles solved by splitting, flipping, and a shameless amount of hashmaps. For once, clever really does beat brute force.”