2131. Longest Palindrome by Concatenating Two Letter Words

Time: O(n)

Space: O(1)

Intuition

Form palindrome pairs from strings. Two strings form a palindrome if one + reverse(other). Count pairs, track longest combined length.

Algorithm

1Sort by length. For each string s: check if reverse(s) exists in set. Longest pair = 2 * longest such length.
2Also check single-string palindromes for the middle (when n is odd number of strings... wait n is pairs).

Common Pitfalls

•Find longest string whose reverse also exists in the list. Answer = 2 * such length.

2131.cs

// Approach: Count word pairs using a 2D frequency array; match reverses, handle double-letter center.
// Time: O(n) Space: O(1)

public class Solution
{
    public int LongestPalindrome(string[] words)
    {
        int ans = 0;

        int[,] count = new int[26, 26];

        foreach (string word in words)
        {
            int i = word[0] - 'a';
            int j = word[1] - 'a';
            if (count[j, i] > 0)
            {
                ans += 4;
                --count[j, i];
            }
            else
                ++count[i, j];
        }

        for (int i = 0; i < 26; i++)
        {
            if (count[i, i] > 0)
                return ans + 2;
        }

        return ans;
    }
}

Was this solution helpful?