Longest Palindrome by Concatenating Two Letter Words

Longest Palindrome by Concatenating Two Letter Words - Problem

You are given an array of strings words. Each element of words consists of two lowercase English letters.

Create the longest possible palindrome by selecting some elements from words and concatenating them in any order. Each element can be selected at most once.

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.

A palindrome is a string that reads the same forward and backward.

Input & Output

Example 1 — Basic Mixed Words

$ Input: words = ["lc","cl","gg"]

› Output: 6

💡 Note: We can form palindrome "gglccllcgg" but since we can use each word at most once, the best we can do is "lccl" using "lc" and "cl" for length 4, or "gg" + something. Actually, we can use all three: "gglccl" isn't palindrome, but "lccl" (length 4) + "gg" separately isn't optimal. The optimal is "ggllcc" rearranged as "gg" + "cl" + "lc" = "ggcllc" which isn't palindrome. Let me recalculate: "cl" + "lc" = "cllc" (length 4) + "gg" unused, or "gg" as center with "cl"+"lc" around it somehow. The answer should be 6 for "lcclgggcllcl" but that uses words multiple times. Actually: "cl"+"gg"+"lc" can form "clgglc" which isn't palindrome. The correct approach: we can form "gglccllcgg" conceptually, but limited to one use each. We get: pair(cl,lc)=4 chars + gg can go in center = 6 total: "lc"+"gg"+"cl" = "cllcgg" rearranged as palindrome "clggcl"? No. Let me think systematically: cl↔lc (reverse pair) = 4 chars, gg↔gg (self pair, use 1) = 2 chars. Total = 6.

Example 2 — Multiple Pairs

$ Input: words = ["ab","ty","yt","lc","cl","ab"]

› Output: 8

💡 Note: We have pairs: ab↔? (ab appears twice, no ba), ty↔yt (1 pair = 4 chars), lc↔cl (1 pair = 4 chars). Total = 4 + 4 = 8 chars. The ab's can't pair with anything so they're unused.

Example 3 — Only Self-Palindromes

$ Input: words = ["cc","ll","xx"]

› Output: 2

💡 Note: All words are self-palindromes (cc, ll, xx). We can use only one as center since each appears once. Maximum length = 2 (using any one word).

Constraints

1 ≤ words.length ≤ 10⁵
words[i].length == 2
words[i] consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Words

Array of two-letter words to choose from

Find Pairs

Match words with their reverses plus self-palindromes

Build Palindrome

Arrange pairs symmetrically with optional center

Key Takeaway

🎯 Key Insight: Palindromes need symmetric word pairs plus at most one center self-palindrome

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is that palindromes need symmetric pairs of words where one word is the reverse of another (like 'ab' and 'ba'), plus optionally one self-palindromic word (like 'aa') in the center. The optimal approach uses frequency counting to pair words efficiently. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2ⁿ × n! × L)	O(n × L)	Generate all possible word combinations and check if they form palindromes
Frequency Count with Pairing	O(n)	O(n)	Count word frequencies and pair complementary words to build palindrome

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible subsets of words
For each subset, try all permutations
Check if concatenated string is palindrome
Track maximum palindrome length

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Create all possible combinations of words

Try Permutations

For each subset, try all orderings

Check Palindrome

Test if concatenation is palindrome

Code -

solution.c — C

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

bool isPalindrome(char* s) {
    int len = strlen(s);
    int left = 0, right = len - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

void swap(char** a, char** b) {
    char* temp = *a;
    *a = *b;
    *b = temp;
}

void permute(char** words, int start, int end, int* maxLength) {
    if (start == end) {
        char concatenated[1000] = "";
        for (int i = 0; i <= end; i++) {
            strcat(concatenated, words[i]);
        }
        if (isPalindrome(concatenated)) {
            int len = strlen(concatenated);
            if (len > *maxLength) {
                *maxLength = len;
            }
        }
        return;
    }
    
    for (int i = start; i <= end; i++) {
        swap(&words[start], &words[i]);
        permute(words, start + 1, end, maxLength);
        swap(&words[start], &words[i]);
    }
}

int solution(char** words, int n) {
    int maxLength = 0;
    
    // Try all possible subsets
    for (int mask = 1; mask < (1 << n); mask++) {
        char* subset[20];
        int subsetSize = 0;
        
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subset[subsetSize++] = words[i];
            }
        }
        
        if (subsetSize > 0) {
            permute(subset, 0, subsetSize - 1, &maxLength);
        }
    }
    
    return maxLength;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple JSON parsing for array of strings
    char* words[100];
    int wordCount = 0;
    
    char* token = strtok(line + 1, ","); // Skip first bracket
    while (token && wordCount < 100) {
        // Remove quotes and spaces
        while (*token == ' ' || *token == '"') token++;
        char* end = token + strlen(token) - 1;
        while (end > token && (*end == ' ' || *end == '"' || *end == ']')) end--;
        *(end + 1) = 0;
        
        words[wordCount] = malloc(strlen(token) + 1);
        strcpy(words[wordCount], token);
        wordCount++;
        
        token = strtok(NULL, ",");
    }
    
    int result = solution(words, wordCount);
    printf("%d\n", result);
    
    // Free memory
    for (int i = 0; i < wordCount; i++) {
        free(words[i]);
    }
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n! × L)

2^n subsets, n! permutations per subset, L length palindrome check

⚠ Quadratic Growth

Space Complexity

O(n × L)

Store permutations and concatenated strings

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 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 - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler