Palindrome Pairs - Practice Coding Problems

Palindrome Pairs - Problem

You are given a 0-indexed array of unique strings words. A palindrome pair is a pair of integers (i, j) such that:

0 <= i, j < words.length
i != j
words[i] + words[j] (the concatenation of the two strings) is a palindrome

Return an array of all the palindrome pairs of words. You must write an algorithm with O(sum of words[i].length) runtime complexity.

Input & Output

Example 1 — Multiple Palindrome Pairs

$ Input: words = ["race","car",".","ecar"]

› Output: [[0,1],[1,0],[3,2]]

💡 Note: "race" + "car" = "racecar" (palindrome), "car" + "race" = "carrace" (not palindrome but "car" + "" would work with different input), "ecar" + "." = "ecar." forms palindrome logic

Example 2 — No Pairs Found

$ Input: words = ["abcd","dcba","lls","s","sssll"]

› Output: [[0,1],[1,0],[3,2],[2,4]]

💡 Note: "abcd" + "dcba" = "abcddcba" (palindrome), "dcba" + "abcd" = "dcbaabcd" (palindrome), "s" + "lls" = "slls" (palindrome), "lls" + "sssll" = "llssssll" (palindrome)

Example 3 — Single Character Edge Case

$ Input: words = ["a",""]

› Output: [[0,1],[1,0]]

💡 Note: "a" + "" = "a" (palindrome), "" + "a" = "a" (palindrome). Both combinations work with empty string.

Constraints

1 ≤ words.length ≤ 5000
0 ≤ words[i].length ≤ 300
words[i] consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Array of unique strings: ["race", "car", ".", "ecar"]

Process

Find pairs where concatenation creates palindromes

Output

Array of index pairs: [[0,1], [1,0], [3,2]]

Key Takeaway

🎯 Key Insight: A palindrome forms when one word can complete another word's palindromic pattern

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

The key insight is that palindromes can be formed by matching word prefixes/suffixes with their reverses. The hash map approach provides efficient O(1) lookups instead of O(n) searches. Best approach uses hash map with prefix/suffix analysis: Time O(n×m²), Space O(n×m).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n² × m)	O(1)	Check every pair of words to see if concatenation forms palindrome
Hash Map with Prefix/Suffix Analysis	O(n × m²)	O(n × m)	Use hash map to store word indices and check prefix/suffix combinations

Brute Force — Algorithm Steps

Iterate through all pairs (i,j) where i ≠ j
Concatenate words[i] + words[j]
Check if concatenation is palindrome
If yes, add [i,j] to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Pair (0,1)

"race" + "car" = "racecar" → palindrome ✓

Check Pair (1,0)

"car" + "race" = "carrace" → not palindrome ✗

Result

Found palindrome pairs: [[0,1], [3,2]]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isPalindrome(char* s) {
    int len = strlen(s);
    for (int i = 0; i < len / 2; i++) {
        if (s[i] != s[len - 1 - i]) {
            return 0;
        }
    }
    return 1;
}

int** solution(char** words, int wordsSize, int* returnSize, int** returnColumnSizes) {
    int** result = (int**)malloc(wordsSize * wordsSize * sizeof(int*));
    *returnColumnSizes = (int*)malloc(wordsSize * wordsSize * sizeof(int));
    int count = 0;
    
    for (int i = 0; i < wordsSize; i++) {
        for (int j = 0; j < wordsSize; j++) {
            if (i != j) {
                char* combined = (char*)malloc(strlen(words[i]) + strlen(words[j]) + 1);
                strcpy(combined, words[i]);
                strcat(combined, words[j]);
                
                if (isPalindrome(combined)) {
                    result[count] = (int*)malloc(2 * sizeof(int));
                    result[count][0] = i;
                    result[count][1] = j;
                    (*returnColumnSizes)[count] = 2;
                    count++;
                }
                free(combined);
            }
        }
    }
    
    *returnSize = count;
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    char** words = (char**)malloc(100 * sizeof(char*));
    int wordsSize = 0;
    
    char* token = strtok(line + 1, ",");
    while (token != NULL) {
        while (*token == ' ' || *token == '"') token++;
        char* end = token + strlen(token) - 1;
        while (end > token && (*end == ' ' || *end == '"' || *end == ']' || *end == '\n')) {
            *end = '\0';
            end--;
        }
        words[wordsSize] = (char*)malloc(strlen(token) + 1);
        strcpy(words[wordsSize], token);
        wordsSize++;
        token = strtok(NULL, ",");
    }
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(words, wordsSize, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[%d,%d]", result[i][0], result[i][1]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × m)

n² pairs to check, each requiring O(m) palindrome validation where m is average word length

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for iteration, no extra data structures

✓ Linear Space

180.0K Views

Medium Frequency

~35 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler