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.

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

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

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

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” ].

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:**

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<=i<n, 0<=j<n, check if words[i] + words[j] is palindrome or not. If we found such a pair of words forming a palindrome then return that pair of words.

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).

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.

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).

`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 <= 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+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 <= k < words[x].length(). `

`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 <= k < length(left_word), time complexity will be O(l^2) for each word left_word. `

`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).`

``

``

```
```