Jobs

Interviews

Discussions

Longest Palindrome After Substring Concatenation I

Medium

Longest Palindrome After Substring Concatenation I

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can you provide more details on the constraints of the input substrings, such as their maximum length or the number of substrings in the input? I'm especially interested in the expected scale of the input to guide my optimization efforts.
Are the substrings case-sensitive? For example, should 'Racecar' be considered a palindrome if the substrings contain mixed-case characters?
If no palindrome can be formed by concatenating two substrings, what should I return? Should I return an empty string, null, or perhaps throw an exception?
Are we only allowed to use each substring once when concatenating to form a palindrome, or can we reuse a substring multiple times?
If multiple palindromes of the same maximum length can be formed, is there a preferred palindrome I should return (e.g., lexicographically smallest, or the one formed by concatenating the substrings in a specific order)?

Brute Force Solution

Approach

The brute force approach to finding the longest palindrome after concatenating substrings involves trying every possible combination of substrings. We create all possible concatenations, check if each is a palindrome, and keep track of the longest one we find. This method guarantees finding the optimal solution, but it does so by exhaustively checking every possibility.

Here's how the algorithm would work step-by-step:

Start by considering every possible way to combine the input substrings.
This means trying the first substring alone, then the first two, then the first three, and so on, all the way to using all of them.
Next, also consider the second substring alone, then the second and third, and so on.
Continue doing this until you have considered every possible combination of substrings.
For each combination of substrings that you create, join them together into one big string.
Check if that big string is a palindrome (reads the same forwards and backwards).
If it is a palindrome, see how long it is.
Keep track of the longest palindrome you find this way.
After checking all possible combinations, the longest palindrome you kept track of is your answer.

Code Implementation

def longest_palindrome_after_substring_concatenation_i(substrings):
    longest_palindrome_length = 0

    # Iterate through all possible starting points for substring combinations
    for start_index in range(len(substrings)):
        for end_index in range(start_index, len(substrings)):
            # Concatenate substrings from start_index to end_index (inclusive)
            concatenated_string = "".join(substrings[start_index:end_index + 1])

            # Check if the concatenated string is a palindrome
            if concatenated_string == concatenated_string[::-1]:

                # Update longest palindrome length if current is longer
                longest_palindrome_length = max(longest_palindrome_length, len(concatenated_string))

    return longest_palindrome_length

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through all possible substrings concatenations, which requires a nested loop structure, contributing O(n^2) where n is the number of input strings. For each concatenated string, the palindrome check takes O(m) time, where m is the length of the concatenated string. In the worst case, m can be proportional to n (if all strings are of similar length and contribute significantly), so checking each string for palindromicity can take O(n) time. Therefore, the overall time complexity is O(n^2 * n) which simplifies to O(n^3).

Space Complexity

O(N) – The brute force approach creates all possible concatenations of substrings. In the worst-case scenario, we might concatenate all N substrings into a single large string to check if it's a palindrome. This resulting concatenated string requires auxiliary space proportional to the total length of the substrings, which can be considered O(N), where N is the total number of characters across all substrings. Additionally, the `longest_palindrome` string variable also requires space proportional to N in the worst case. Therefore, the space complexity is O(N).

Optimal Solution

Approach

The most efficient way to solve this problem is to focus on building the longest palindrome by strategically combining substrings. We'll use a method to find pairs of substrings that can form palindromes, and also look for substrings that are palindromes by themselves. This allows us to construct the overall longest palindrome without exhaustively checking every possible combination.

Here's how the algorithm would work step-by-step:

Count how many times each substring appears in the input.
Look for substring pairs that are reverse versions of each other; these can be combined to form larger palindromes. For example, if you have 'ab' and 'ba', combine them.
For each such pair, add their combined length to a running total of the length of the palindrome you're building.
If any substrings are palindromes by themselves (like 'aa' or 'aba'), check if there is an odd number of them. If there is at least one, we can put it in the center of our palindrome to increase the length by the substring's length.
Combine the length of the paired substrings and the central palindrome substring (if any) to get the length of the longest possible palindrome.
If you found no suitable pairs but a palindrome by itself existed, the longest palindrome possible is the palindrome string itself. Otherwise, the longest palindrome is an empty string with length 0.

Code Implementation

def longest_palindrome_after_substring_concatenation(substrings):
    substring_counts = {}
    for substring in substrings:
        substring_counts[substring] = substring_counts.get(substring, 0) + 1

    longest_palindrome_length = 0
    central_palindrome_exists = False

    #Combine pairs of reversed substrings to form palindrome.
    for substring, count in substring_counts.items():
        reversed_substring = substring[::-1]

        if substring != reversed_substring and reversed_substring in substring_counts:
            pairs_to_combine = min(count, substring_counts[reversed_substring])
            longest_palindrome_length += 2 * len(substring) * pairs_to_combine
            substring_counts[substring] -= pairs_to_combine
            substring_counts[reversed_substring] -= pairs_to_combine

        #Handle palindromic substrings.
        elif substring == reversed_substring:

            #If substring is palindrome by itself.
            if count % 2 == 0:
                longest_palindrome_length += len(substring) * count
                substring_counts[substring] = 0
            else:
                longest_palindrome_length += len(substring) * (count - 1)
                central_palindrome_exists = True #Mark that a center palindrome exists.
                substring_counts[substring] = 1

    #If a central palindrome exists, add its length to overall length.
    if central_palindrome_exists:
        for substring, count in substring_counts.items():
            if substring == substring[::-1] and count > 0:
                longest_palindrome_length += len(substring)
                break

    return longest_palindrome_length

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the number of substrings and m be the maximum length of a substring. Counting the occurrences of each substring takes O(n*m) time where we iterate through all substrings of at most length m. Finding reverse pairs and palindrome substrings involves iterating through the substring counts, which is O(n). String comparison for reverse operations also takes O(m). Therefore, the dominating factor becomes O(n*m), making the overall time complexity O(n*m).

Space Complexity

O(N) – The algorithm primarily uses a hash map (or counter) to store the frequency of each substring, where N is the total number of substrings in the input. In the worst case, all substrings could be unique, requiring space proportional to the number of substrings. Therefore, the auxiliary space required grows linearly with the number of substrings N, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty array of strings	Return an empty string since no concatenation is possible.
Array with a single string	Return the single string if it's a palindrome; otherwise return an empty string.
Array with two strings that form a palindrome when concatenated in either order	Choose the longer palindrome if string lengths differ or any valid palindrome if they are equal length.
Array with strings that do not form any palindrome after concatenation	Return an empty string.
Array with null or empty strings mixed with valid strings	Treat null or empty strings as valid strings with length 0.
Array with very long strings that could cause memory issues or performance bottlenecks during palindrome checks	Implement efficient palindrome check (e.g., two-pointer approach) and consider limiting maximum string length if necessary.
All strings are identical	Concatenate any two strings in the array to check for a palindrome, and return if a palindrome exists.
Large number of strings in array leading to quadratic time complexity.	Check for more optimal approaches involving HashMaps for efficient palindrome substring matching.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can you provide more details on the constraints of the input substrings, such as their maximum length or the number of substrings in the input? I'm especially interested in the expected scale of the input to guide my optimization efforts.
Are the substrings case-sensitive? For example, should 'Racecar' be considered a palindrome if the substrings contain mixed-case characters?
If no palindrome can be formed by concatenating two substrings, what should I return? Should I return an empty string, null, or perhaps throw an exception?
Are we only allowed to use each substring once when concatenating to form a palindrome, or can we reuse a substring multiple times?
If multiple palindromes of the same maximum length can be formed, is there a preferred palindrome I should return (e.g., lexicographically smallest, or the one formed by concatenating the substrings in a specific order)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering every possible way to combine the input substrings.
This means trying the first substring alone, then the first two, then the first three, and so on, all the way to using all of them.
Next, also consider the second substring alone, then the second and third, and so on.
Continue doing this until you have considered every possible combination of substrings.
For each combination of substrings that you create, join them together into one big string.
Check if that big string is a palindrome (reads the same forwards and backwards).
If it is a palindrome, see how long it is.
Keep track of the longest palindrome you find this way.
After checking all possible combinations, the longest palindrome you kept track of is your answer.

Code Implementation

def longest_palindrome_after_substring_concatenation_i(substrings):
    longest_palindrome_length = 0

    # Iterate through all possible starting points for substring combinations
    for start_index in range(len(substrings)):
        for end_index in range(start_index, len(substrings)):
            # Concatenate substrings from start_index to end_index (inclusive)
            concatenated_string = "".join(substrings[start_index:end_index + 1])

            # Check if the concatenated string is a palindrome
            if concatenated_string == concatenated_string[::-1]:

                # Update longest palindrome length if current is longer
                longest_palindrome_length = max(longest_palindrome_length, len(concatenated_string))

    return longest_palindrome_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Count how many times each substring appears in the input.
Look for substring pairs that are reverse versions of each other; these can be combined to form larger palindromes. For example, if you have 'ab' and 'ba', combine them.
For each such pair, add their combined length to a running total of the length of the palindrome you're building.
If any substrings are palindromes by themselves (like 'aa' or 'aba'), check if there is an odd number of them. If there is at least one, we can put it in the center of our palindrome to increase the length by the substring's length.
Combine the length of the paired substrings and the central palindrome substring (if any) to get the length of the longest possible palindrome.
If you found no suitable pairs but a palindrome by itself existed, the longest palindrome possible is the palindrome string itself. Otherwise, the longest palindrome is an empty string with length 0.

Code Implementation

def longest_palindrome_after_substring_concatenation(substrings):
    substring_counts = {}
    for substring in substrings:
        substring_counts[substring] = substring_counts.get(substring, 0) + 1

    longest_palindrome_length = 0
    central_palindrome_exists = False

    #Combine pairs of reversed substrings to form palindrome.
    for substring, count in substring_counts.items():
        reversed_substring = substring[::-1]

        if substring != reversed_substring and reversed_substring in substring_counts:
            pairs_to_combine = min(count, substring_counts[reversed_substring])
            longest_palindrome_length += 2 * len(substring) * pairs_to_combine
            substring_counts[substring] -= pairs_to_combine
            substring_counts[reversed_substring] -= pairs_to_combine

        #Handle palindromic substrings.
        elif substring == reversed_substring:

            #If substring is palindrome by itself.
            if count % 2 == 0:
                longest_palindrome_length += len(substring) * count
                substring_counts[substring] = 0
            else:
                longest_palindrome_length += len(substring) * (count - 1)
                central_palindrome_exists = True #Mark that a center palindrome exists.
                substring_counts[substring] = 1

    #If a central palindrome exists, add its length to overall length.
    if central_palindrome_exists:
        for substring, count in substring_counts.items():
            if substring == substring[::-1] and count > 0:
                longest_palindrome_length += len(substring)
                break

    return longest_palindrome_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty array of strings	Return an empty string since no concatenation is possible.
Array with a single string	Return the single string if it's a palindrome; otherwise return an empty string.
Array with two strings that form a palindrome when concatenated in either order	Choose the longer palindrome if string lengths differ or any valid palindrome if they are equal length.
Array with strings that do not form any palindrome after concatenation	Return an empty string.
Array with null or empty strings mixed with valid strings	Treat null or empty strings as valid strings with length 0.
Array with very long strings that could cause memory issues or performance bottlenecks during palindrome checks	Implement efficient palindrome check (e.g., two-pointer approach) and consider limiting maximum string length if necessary.
All strings are identical	Concatenate any two strings in the array to check for a palindrome, and return if a palindrome exists.
Large number of strings in array leading to quadratic time complexity.	Check for more optimal approaches involving HashMaps for efficient palindrome substring matching.