Forming the Longest Palindrome by Concatenating Array Strings

Given an array of X strings in which each string consists of two lowercase English letters, join as many strings together as possible in order to obtain a palindrome.

Input: arr = [“ck”, “kc”, “ho”, “kc”] Output: 4

explanation being that the longest palindrome are “ckkc” and “kcck” which both have lengths of 4.

Google phone screen question.

Problem Explanation

You have an array of strings, each containing exactly two lowercase letters. You can concatenate these strings in any order to create a longer string. The goal is to form the longest palindrome possible. The length of this palindrome is the output.

Key Insights

1. A palindrome reads the same forward and backward.
2. For each string, its reverse must also exist in the array to form a palindrome.

Approach

1. Initialize Count: Start with a variable count set to 0. This variable will hold the length of the longest palindrome.

2. Hash Table: Create a hash table (dictionary) to store the frequency of each string in the array.

3. Find Pairs: For each string in the array, check if its reverse exists in the hash table.

• If it exists, you can form a palindrome with these two strings. Remove both strings from the hash table and add 4 to count.

4. Check Remaining Strings: Some strings may still be left in the hash table. They can’t form a palindrome with any other string, but if they are palindromes themselves, one of them can be placed in the middle of the final string to increase the length by 2.

• Check if any string is a palindrome. If yes, add 2 to count.

5. Return Count: The value in count is the length of the longest palindrome that can be formed. Return this value.

Code

Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def longestPalindrome(arr):
    count = 0
    hash_table = {}
    
    # Step 2: Populate hash table
    for s in arr:
        if s in hash_table:
            hash_table[s] += 1
        else:
            hash_table[s] = 1

    # Step 3: Find pairs and update count
    for s in arr:
        reverse_s = s[::-1]
        if s in hash_table and reverse_s in hash_table:
            if hash_table[s] > 0 and hash_table[reverse_s] > 0:
                count += 4
                hash_table[s] -= 1
                hash_table[reverse_s] -= 1

    # Step 4: Check for palindromic strings
    for s in hash_table:
        if s == s[::-1] and hash_table[s] > 0:
            count += 2
            break

    # Step 5: Return the count
    return count

Test the Function

1

print(longestPalindrome(["ck", "kc", "ho", "kc"]))  # Output should be 4

This function should solve the problem efficiently.