Hi, I recently did an OA for Databricks and got the following question. I'm not sure how to solve it efficiently, therefore I would appreciate any advice on DP approaches and recursion approaches (with memoisation), amongst any others that may exist.

Longest Palindrome with Pairs of Characters (Paraphased):

Input:

We're given an array of length N containing 2-letter strings.

Output:

We have to return the length of the longest palindrome that can be created by joining as many of these strings together.

Example 1:

Input: ["gh, "bc", "hg"]
Output: 4
Explanation: We can join "gh" and "hg" to get a palindrome "ghhg" of length 4. Similarly, we can join "hg" with "gh" to get a palindrome "hggh" of length 4 as well.

Example 2:

Input: ["gh, "bc", "hg", "bb"]
Output: 6
Explanation: We can join "gh", "bb", and "hg" to get a palindrome "ghbbhg" of length 6. Similarly, we can join "hg", "bb", and "gh" to get a palindrome "hgbbgh" of length 6 as well.

Note:

The order does not matter. That means, we can use Arr[1] + Arr[2] + Arr[0] for an array of size 3, if that forms the longest palindrome.
i.e. Arr = ["ab", "ba", "cc"] gives the longest palindrome "baccab" of length 6.