2131. Longest Palindrome by Concatenating Two Letter Words

Longest Palindrome by Concatenating Two-Letter Words

Problem Description

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.

 

Example 1:

Input: words = ["lc","cl","gg"]
Output: 6

Explanation: One longest palindrome is "lc" + "gg" + "cl" = "lcggcl", of length 6.
Note that "clgglc" is another longest palindrome that can be created.

Example 2:

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

Explanation: One longest palindrome is "ty" + "lc" + "cl" + "yt" = "tylcclyt", of length 8.
Note that "lcyttycl" is another longest palindrome that can be created.

Example 3:

Input: words = ["cc","ll","xx"]
Output: 2

Explanation: One longest palindrome is "cc", of length 2.
Note that "ll" is another longest palindrome that can be created, and so is "xx".

 

Constraints:

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

Approach) HashTable (hashmap)

/**
 * @param {string[]} words
 * @return {number}
 */
var longestPalindrome = function (words) {
  // store the word in a map with total count
  const map = {};
  let count = 0;

  for (const word of words) {
    if (!map[word]) map[word] = 1;
    else {
      map[word] += 1;
    }
  }

  let flag = false;
  for (const word of words) {
    const reverse = word[1] + word[0];
    if (word === reverse) {
      while (map[word] >= 2) {
        map[word] -= 2;
        count += 4;
      }
      if (map[word] === 1 && !flag) {
        // only we need to take one word with same pairs which give us an advantage for center letter pair
        // anymore similar pair will not help so we make flag to true
        flag = true;
        count += 2;
        map[word] -= 1;
      }
      continue;
    }
    while (map[word] > 0 && map[reverse] > 0) {
      map[word] -= 1;
      map[reverse] -= 1;
      count += 4;
    }
  }

  return count;
};

Approach) Another HashTable (hashmap)

var longestPalindrome = function(words) {
    var mp = {};
    var count = 0;
    let selfPalindrones = 0;
    for(var i = 0; i< words.length; i++) {
        let rev = words[i][1] + words[i][0];
        if(mp[words[i]]) {
            if(rev == words[i]) selfPalindrones -= 1;
            mp[words[i]]--;
            count+=2;
        } else {
            if(rev==words[i]) {
                selfPalindrones +=1;
            }
            if(!mp[rev]) {
                mp[rev] = 1;
            } else {
                mp[rev]++;
            }
        }
    }
    return selfPalindrones>0 ? 2 + count*2 : count*2;
};

Approach) Neat: frequency

const longestPalindrome = (words) => {
    const frequency = words.reduce((dic, x) => (dic[x] = (dic[x] || 0) + 1, dic), {})
    let pairs = 0, central = 0
    for (const word in frequency)
        if (word[0] === word[1]) {
            central |= frequency[word] % 2
            pairs += 2 * Math.floor(frequency[word] / 2)
        } 
        else if (word[1] + word[0] in frequency)
            pairs += Math.min(frequency[word], frequency[word[1] + word[0]])
    return 2 * (pairs + central)
}

Approach) Greedy - hashtable

/**
 * @param {string[]} words
 * @return {number}
 */
var longestPalindrome = function(words) {
    let hash = {};
    let longest = 0;
    // Build hash table with unique strings and collision rate
    for (let word of words) {
        if (hash[word]) {
            hash[word] += 1;
        } else {
            hash[word] = 1;
        }
    }
    let flag = false;
    // Loop through words to check if reverse string exists inside table
    for (let word of words) {
        let reverse = word[1] + word[0];
        // If word is equal to reverse and it only occurs one time, note it down to add 2 later
        if (word === reverse && hash[word] === 1) {
            flag = true;
        }
        // If word is equal to reverse and it occurs multiple times
        else if (word === reverse && hash[word] > 1) {
            // Add 4 to longest as long as there are multiples of two > 1
            while (hash[word] > 1) {
                longest += 4;
                hash[word] -= 2;
            }
            // If word is equal to reverse and there is only 1 leftover, note it down to add 2 later if we have not already accounted it for another pair
            if (hash[word] === 1) flag = true;
        }
        // Check if there is another string inside of our array that is the reverse of our current word
        else if (hash[reverse]) {
            // Add both string lengths as long as both strings collision rate is greater then one
            while (hash[reverse] > 0 && hash[word] > 0) {
                longest += 4;
                hash[reverse] -= 1;
                hash[word] -= 1;
            }
        }
    }
    // Add 2 if there was a string that had equal chars. This is the string in the middle of your palindrome 
    flag ? longest += 2 : longest += 0;
    return longest;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #2131. Longest Palindrome by Concatenating Two-Letter Words

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!