Longest palindrome by concatenating two letter words

Array Hash Table String Greedy Counting

53.5% acceptance

Feb 25, 2026

2951

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_palindrome(words: Vec<String>) -> i32 {
    use std::collections::HashMap;
    let mut count: HashMap<[u8; 2], i32> = HashMap::new();
    for w in &words {
      let b = w.as_bytes();
      *count.entry([b[0], b[1]]).or_default() += 1;
    }

    let mut len = 0i32;
    let mut has_center = false;

    for (&[a, b], &cnt) in &count {
      if a == b {
        // Palindromic word (like "aa")
        len += (cnt / 2) * 4;
        if cnt % 2 == 1 {
          has_center = true;
        }
      } else if a < b {
        // Non-palindromic: pair with reverse [b, a]
        let rev_cnt = *count.get(&[b, a]).unwrap_or(&0);
        len += cnt.min(rev_cnt) * 4;
      }
    }

    if has_center {
      len += 2;
    }
    len
  }
}