Longest Palindrome by Concatenating Two-Letter Words

Problem#

Given an array of 2-letter strings words, build the longest palindrome by concatenating some of them. Return its length, or 0 if impossible.

Examples#

words = ["lc","cl","gg"] → 6 ("lcggcl").
words = ["ab","ty","yt","lc","cl","ab"] → 8 ("tylcclyt").
words = ["cc","ll","xx"] → 2.

Constraints#

1 <= words.length <= 10^5, words are length 2, lowercase letters.

Hints#

Hint

For each word xy, pair it with yx. Same-letter words (aa, bb, etc.) can be placed at the palindrome’s center once.

Approach#

Count word frequencies. For each word w = xy: if x != y, pair as many copies of w as we have of its reverse yx — contributes 4 * min(cnt[w], cnt[yx]) to the answer (divide by 2 to avoid double-counting). For x == y, pair up cnt[w] / 2 pairs (contributing 4 * pairs); reserve one same-letter word as the center if any has odd count.

Solution#

class Solution {
public:
    int longestPalindrome(vector<string>& words) {
        unordered_map<string,int> cnt;
        for (auto& w : words) ++cnt[w];
        int ans = 0;
        bool centerAvail = false;
        for (auto& [w, c] : cnt) {
            string rev = {w[1], w[0]};
            if (w == rev) {
                ans += (c / 2) * 4;
                if (c & 1) centerAvail = true;
            } else if (w < rev) {       // count each unordered pair once
                auto it = cnt.find(rev);
                if (it != cnt.end()) ans += min(c, it->second) * 4;
            }
        }
        if (centerAvail) ans += 2;
        return ans;
    }
};

func longestPalindrome(words []string) int {
    cnt := map[string]int{}
    for _, w := range words {
        cnt[w]++
    }
    ans := 0
    centerAvail := false
    for w, c := range cnt {
        rev := string([]byte{w[1], w[0]})
        if w == rev {
            ans += (c / 2) * 4
            if c&1 == 1 {
                centerAvail = true
            }
        } else if w < rev {
            if c2, ok := cnt[rev]; ok {
                if c < c2 {
                    ans += c * 4
                } else {
                    ans += c2 * 4
                }
            }
        }
    }
    if centerAvail {
        ans += 2
    }
    return ans
}

from collections import Counter
from typing import List

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        cnt = Counter(words)
        ans = 0
        center_avail = False
        for w, c in cnt.items():
            rev = w[1] + w[0]
            if w == rev:
                ans += (c // 2) * 4
                if c & 1:
                    center_avail = True
            elif w < rev:
                if rev in cnt:
                    ans += min(c, cnt[rev]) * 4
        if center_avail:
            ans += 2
        return ans

function longestPalindrome(words) {
    const cnt = new Map();
    for (const w of words) cnt.set(w, (cnt.get(w) ?? 0) + 1);
    let ans = 0;
    let centerAvail = false;
    for (const [w, c] of cnt.entries()) {
        const rev = w[1] + w[0];
        if (w === rev) {
            ans += Math.floor(c / 2) * 4;
            if (c & 1) centerAvail = true;
        } else if (w < rev) {
            const c2 = cnt.get(rev);
            if (c2 !== undefined) ans += Math.min(c, c2) * 4;
        }
    }
    if (centerAvail) ans += 2;
    return ans;
}

class Solution {
    public int longestPalindrome(String[] words) {
        Map<String, Integer> cnt = new HashMap<>();
        for (String w : words) cnt.merge(w, 1, Integer::sum);
        int ans = 0;
        boolean centerAvail = false;
        for (Map.Entry<String, Integer> e : cnt.entrySet()) {
            String w = e.getKey();
            int c = e.getValue();
            String rev = "" + w.charAt(1) + w.charAt(0);
            if (w.equals(rev)) {
                ans += (c / 2) * 4;
                if ((c & 1) == 1) centerAvail = true;
            } else if (w.compareTo(rev) < 0) {
                Integer c2 = cnt.get(rev);
                if (c2 != null) ans += Math.min(c, c2) * 4;
            }
        }
        if (centerAvail) ans += 2;
        return ans;
    }
}

function longestPalindrome(words: string[]): number {
    const cnt = new Map<string, number>();
    for (const w of words) cnt.set(w, (cnt.get(w) ?? 0) + 1);
    let ans = 0;
    let centerAvail = false;
    for (const [w, c] of cnt.entries()) {
        const rev = w[1] + w[0];
        if (w === rev) {
            ans += Math.floor(c / 2) * 4;
            if (c & 1) centerAvail = true;
        } else if (w < rev) {
            const c2 = cnt.get(rev);
            if (c2 !== undefined) ans += Math.min(c, c2) * 4;
        }
    }
    if (centerAvail) ans += 2;
    return ans;
}

Editorial#

The w < rev guard prevents counting each (w, rev) pair twice. Same-letter words xx are special: they can pair with another copy of xx (each pair contributes 4 letters), and one leftover odd xx can sit in the palindrome’s center contributing 2 more letters. Only one center is allowed regardless of how many such words have odd counts.

Complexity#

Time: O(N).
Space: O(N).

Longest Palindrome by Concatenating Two-Letter Words

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#