About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Join Words To Make a Palindrome Problem

Given a list of strings words, of size n, check if there is any pair of words that can be joined (in any order) to form a palindrome then return the pair of words forming palindrome.

Example One

Input: words = [ “bat”, “tab”, “zebra” ]

Output: result = [ “bat”, “tab” ]

As “bat” + “tab” = “battab”, which is a palindrome.

Example Two

Input: words = [ “ant”, “dog”, “monkey” ]

Output: result = [ “NOTFOUND”, “DNUOFTON” ]

As for each 6 combinations of string of words, there is no single generated word which is a palindrome hence result list will be [ “NOTFOUND”, “DNUOFTON” ].

Notes

Input Format: Only argument for function, list of strings words.

Output:

Return a pair of words (i.e. list of string result of size 2 such that result[0] + result[1] is a palindrome).

In case of multiple answers return any one of them.

In case of no answer return list [“NOTFOUND”, “DNUOFTON”].


Solutions

Below are the two solutions

1) brute_force_solution.java

A naive approach would be to iterate over all ordered pairs of words from list words, i.e. (words[i], words[j]) such that i != j, 0

Time Complexity:

O((n^2)*l), where n is size of list words and l is the maximum length of words in list words.

As there are total 2*(nC2) ordered pair of words, and for each pair, for finding whether that pair is forming palindrome or not will take O(l).So, time complexity of this solution will be O((n^2)*l).

Auxiliary Space Used:

O(l) where l is the maximum length of words in list words.

As we are storing result list of two words of maximum length l.

Space Complexity:

O(n*l) where n is size of list words and l is the maximum length of words in list words.

Input will take space O(n*l) because we are storing n words of list words where maximum possible length of word can be l and auxiliary space used is O(l). So, O(n*l) + O(l) -> O(n*l).


// -------- START --------
    static String[] join_words_to_make_a_palindrome(String words[]) {
        String result[] = new String[2];
        result[0] = "NOTFOUND";
        result[1] = "DNUOFTON";

        int n = words.length;
        // Iterating over all possible pair (i,j), 0<=i


2) optimal_solution.java

A better approach would be as follows from some observations:

Let's say there exists a pair of words (words[x], words[y]), such that result = (words[x] + words[y]) is a palindrome.

Two cases are possible here:

CASE 1: words[x].length() >= words[y].length()

Iterating over words, considering the word in the current iteration as xth word in words. Task is to find out if there exists some yth word, such that words[x] + words[y] is a palindrome. Now, if such y exists, it must be of the form stringReverse(words[x].substring(0, k)), for some 0

So, now we only need to find such k, such that (words[y] == stringReverse(words[x].substring(0, k))) and (words[x].substring(k+1, words[x].length())) is a palindrome, if (k+1< words[x].length())

CASE 2: words[x].length() < words[y].length()

Iterating over words, considering the word in the current iteration as xth word in words. Task is to find out if there exists some yth word, such that words[y] + words[x] is a palindrome. Now, if such y exists, it must be of the form stringReverse(words[x].substring(k, words[x].length())), for some 0

So, now we only need to find such k, such that (words[y] == stringReverse(words[x].substring(k, words[x].length()))) and (words[x].substring(0, k)) is a palindrome, if (k>0)

Both cases require a quick lookup of words in list words. So, we can use hashset or hashMap here for constant time (amortized time) lookup of words. Also, in some cases, for eg. "aaaaa", we need to know the frequency of words so that same word (same indexed word in list of words) doesn't get picked up as another word to make a palindrome. So, a hashmap having word as key and frequency of that word as value will work here. See the implementation for better understanding.

Time Complexity:

O(n*(l^2)) where n is size of list words and l is the maximum length of words in list words.

As while iterating over list of words, considering the word in current iteration as left_word, we have to do two lookups and two palindrome check for each k, 0

So, total time complexity will be O(n*(l^2)).

Auxiliary Space Used:

O(n*l) where n is size of list words and l is the maximum length of words in list words.

As we are maintaining a hashmap of frequencies of words for n words of list words, space complexity to maintain this will be O(n*l) and we are storing result list of two words of maximum length l.

O(n*l) + O(l) → O(n*l)

Space Complexity:

O(n*l) where n is size of list words and l is the maximum length of words in list words.

Input will take space O(n*l) because we are storing n words of list words where maximum possible length of word can be l and auxiliary space used is O(n*l). So, O(n*l) +

O(n*l) -> O(n*l).


// -------- START --------
    static String[] join_words_to_make_a_palindrome(String words[]) {
        String result[] = new String[2];
        result[0] = "NOTFOUND";
        result[1] = "DNUOFTON";

        HashMap count = new HashMap();
        for(String word: words){
            if(count.containsKey(word)){
                count.put(word, count.get(word)+1);
            }else{
                count.put(word, 1);
            }
        }
        // To find (left_word + right_word) exist which form palindrome where 
        // left_word and right_word in given list of words
        String current = "";
        
        for(String left_word: words){
            
            current = "";
            // Two cases are possible here:
            // 
            // CASE 1: words[x].length() >= words[y].length()
            
            // Iterating over words, considering the word in the current iteration as xth word in words.
            // Task is to find out if there exists some yth word, such that 
            // words[x] + words[y] is a palindrome. 
            // Now, if such y exists, it must be of the form
            // stringReverse(words[x].substring(0, k)), for some 0 <= k < words[x].length(). 
            // So, now we only need to find such k,
            // such that (words[y] == stringReverse(words[x].substring(0, k))) and 
            // (words[x].substring(k+1,words[x].length())) is a palindrome, if (k+11){
                            result[0] = left_word;
                            result[1] = current;
                            return result;
                        }