Longest Palindrome by Concatenating Two Letter Words

Medium
1233.

Longest Palindrome by Concatenating Two Letter Words

Longest Palindrome by Concatenating Two Letter Words is a medium coding problem on arrays, strings and hash table, asked in Amazon, Google, Microsoft and Databricks interviews.

You are given an array words; every word consists of exactly two lowercase letters.

Pick some of the words (each array element at most once) and concatenate them in any order you like to form a palindrome — a string that reads the same forwards and backwards.

Return the length of the longest palindrome you can build, or 0 if you cannot build any.

Example 1

Input
words = ["ka","ak","oo","oo","oo","co"]
Output
10
Explanation
`"ka" + "oo" + "oo" + "oo" + "ak"` gives `"kaooooooak"`. `"co"` has no partner `"oc"`.

Example 2

Input
words = ["ab","cd","ef"]
Output
0

Example 3

Input
words = ["xx"]
Output
2
Explanation
A single word with two equal letters is a palindrome by itself.

Constraints

  • 1 <= words.length <= 10^5
  • words[i].length == 2
  • words[i] consists of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @return {number}
 */
var longestPalindrome = function(words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Palindrome by Concatenating Two Letter Words Solution

Longest Palindrome by Concatenating Two Letter Words solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Longest Palindrome by Concatenating Two Letter Words is a medium coding problem on arrays, strings and hash table, asked in Amazon, Google, Microsoft and Databricks interviews.

Problem statement

You are given an array words; every word consists of exactly two lowercase letters.

Pick some of the words (each array element at most once) and concatenate them in any order you like to form a palindrome — a string that reads the same forwards and backwards.

Return the length of the longest palindrome you can build, or 0 if you cannot build any.

Example 1

Input: words = ["ka","ak","oo","oo","oo","co"]
Output: 10
Explanation: `"ka" + "oo" + "oo" + "oo" + "ak"` gives `"kaooooooak"`. `"co"` has no partner `"oc"`.

Example 2

Input: words = ["ab","cd","ef"]
Output: 0

Example 3

Input: words = ["xx"]
Output: 2
Explanation: A single word with two equal letters is a palindrome by itself.

Constraints

  • 1 <= words.length <= 10^5
  • words[i].length == 2
  • words[i] consists of lowercase English letters

Hints for Longest Palindrome by Concatenating Two Letter Words

  1. Hint 1

    In a palindrome built from two-letter blocks, the block at position i from the left mirrors the block at position i from the right.

  2. Hint 2

    So a word xy with x != y can only be used together with a copy of yx. A word xx can pair with another xx.

  3. Hint 3

    Count the words. Pair xy with yx as often as possible, pair xx with xx, and if any xx is left over, put one in the middle.

How to solve Longest Palindrome by Concatenating Two Letter Words

Words go in mirrored pairs around the centre: xy needs a yx, xx needs another xx. At most one unpaired xx can sit in the very middle.

Approach

  1. Count every word in a 26 × 26 table cnt[x][y].
  2. For each pair of letters x < y, add 4 × min(cnt[x][y], cnt[y][x]).
  3. For each letter x, add 4 × floor(cnt[x][x] / 2), and remember whether any cnt[x][x] is odd.
  4. If some xx word was left over, add 2 for the centre.

Why it works

Because every word has length 2 and the palindrome is a concatenation of words, the blocks align: the i-th word from the left is the reverse of the i-th word from the right, except possibly one word exactly in the middle, which must then be a palindrome itself (xx). Hence every usable word except the centre is matched with its reverse, the count of xy pairs is limited by the rarer of xy and yx, and greedily using all such pairs plus one spare xx is optimal.

Complexity

  • Time — O(n + 26²)
  • Space — O(26²)

Pitfalls

  • Only one leftover xx can be placed in the middle, even if several letters have odd counts.
  • Do not count an xy/yx pair twice by visiting both orders — loop over x < y only.
  • A word xy with x != y can never be the centre.

Reference solution

Python

from typing import List

def longestPalindrome(words: List[str]) -> int:
    cnt = [[0] * 26 for _ in range(26)]
    for w in words:
        cnt[ord(w[0]) - 97][ord(w[1]) - 97] += 1
    length = 0
    center = False
    for x in range(26):
        length += (cnt[x][x] // 2) * 4
        if cnt[x][x] % 2 == 1:
            center = True
        for y in range(x + 1, 26):
            length += min(cnt[x][y], cnt[y][x]) * 4
    return length + (2 if center else 0)

Java

public static int longestPalindrome(String[] words) {
    int[][] cnt = new int[26][26];
    for (String w : words) cnt[w.charAt(0) - 'a'][w.charAt(1) - 'a']++;
    int len = 0;
    boolean center = false;
    for (int x = 0; x < 26; x++) {
        len += (cnt[x][x] / 2) * 4;
        if (cnt[x][x] % 2 == 1) center = true;
        for (int y = x + 1; y < 26; y++) len += Math.min(cnt[x][y], cnt[y][x]) * 4;
    }
    return len + (center ? 2 : 0);
}

C++

int longestPalindrome(vector<string>& words) {
    int cnt[26][26] = {{0}};
    for (auto& w : words) cnt[w[0] - 'a'][w[1] - 'a']++;
    int len = 0;
    bool center = false;
    for (int x = 0; x < 26; x++) {
        len += (cnt[x][x] / 2) * 4;
        if (cnt[x][x] % 2 == 1) center = true;
        for (int y = x + 1; y < 26; y++) len += min(cnt[x][y], cnt[y][x]) * 4;
    }
    return len + (center ? 2 : 0);
}

JavaScript

var longestPalindrome = function(words) {
    var cnt = [];
    for (var i = 0; i < 26; i++) cnt.push(new Array(26).fill(0));
    for (var w = 0; w < words.length; w++) cnt[words[w].charCodeAt(0) - 97][words[w].charCodeAt(1) - 97]++;
    var len = 0, center = false;
    for (var x = 0; x < 26; x++) {
        len += Math.floor(cnt[x][x] / 2) * 4;
        if (cnt[x][x] % 2 === 1) center = true;
        for (var y = x + 1; y < 26; y++) len += Math.min(cnt[x][y], cnt[y][x]) * 4;
    }
    return len + (center ? 2 : 0);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings