Join Words To Make A Palindrome Problem Statement
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
{
"words": ["bat", "tab", "zebra"]
}
Output:
["bat", "tab"]
As "bat" + "tab" = "battab", which is a palindrome.
Example Two
{
"words": ["ant", "dog", "monkey"]
}
Output:
["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
- If there are multiple correct answers, return any one.
- In case of no answer return list
["NOTFOUND", "DNUOFTON"].
Constraints:
- 1 <= length of a word <= 30
- 2 <=
n <= 20000
- Words consist of characters
['a'-'z'], ['A'-'Z'], ['0'-'9']
We have provided two solutions. We will refer to the size of list words as n and maximum length of words in words as l.
Join Words To Make A Palindrome Solution 1: Brute Force
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.
Time Complexity
O(n2 * l).
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(n2 * l).
Auxiliary Space Used
O(l).
As we are storing result list of two words of maximum length l.
Space Complexity
O(n * l).
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).
Code For Join Words To Make A Palindrome Solution 1: Brute Force
/*
* Asymptotic complexity in terms of size of list \`words\` \`n\` and maximum length of words in \`words\` \`l\`:
* Time: O(n^2 * l).
* Auxiliary space: O(l).
* Total space: O(n * l).
*/
static ArrayList<String> join_words_to_make_a_palindrome(ArrayList<String> words) {
ArrayList<String> result = new ArrayList<String>(Collections.nCopies(2, ""));
result.set(0, "NOTFOUND");
result.set(1, "DNUOFTON");
int n = words.size();
// Iterating over all possible pair (i, j), 0 <= i < j < n
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (isPalindrome(words.get(i) + words.get(j))) {
result.set(0, words.get(i));
result.set(1, words.get(j));
return result;
}
if (isPalindrome(words.get(j) + words.get(i))) {
result.set(0, words.get(j));
result.set(1, words.get(i));
return result;
}
}
}
return result;
}
static boolean isPalindrome(String str) {
int index = 0;
int n = str.length();
while(index < n - index) {
if(str.charAt(index) != str.charAt(n - index - 1)) {
return false;
}
index++;
}
return true;
}
Join Words To Make A Palindrome Solution 2: Optimal
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 * l2).
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(l2) for each word left_word.
So, total time complexity will be O(n * l2).
Auxiliary Space Used
O(n * l).
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).
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).
Code For Join Words To Make A Palindrome Solution 2: Optimal
/*
* Asymptotic complexity in terms of size of list \`words\` \`n\` and maximum length of words in \`words\` \`l\`:
* Time: O(n * l^2).
* Auxiliary space: O(n * l).
* Total space: O(n * l).
*/
static ArrayList<String> join_words_to_make_a_palindrome(ArrayList<String> words) {
ArrayList<String> result = new ArrayList<String>(Collections.nCopies(2, ""));
result.set(0, "NOTFOUND");
result.set(1, "DNUOFTON");
HashMap<String, Integer> count = new HashMap<String, Integer>();
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 + 1 < words[x].length())
for(int j = 0; j < left_word.length(); j++){
// Here, current string denotes stringreverse(left_word.substring(0, j))
// Check if current string is present in words or not
current = left_word.charAt(j) + current;
if(count.containsKey(current)){
// Handles that case so that same string itself doesn't get picked up as other string in pair to
// form a palindrome
if(current.equals(left_word)){
if(count.get(current) > 1){
result.set(0, left_word);
result.set(1, current);
return result;
}
}
// Check if left_word.substring(j + 1, len(left_word)) is a palindrome or not
else if(isPalindrome(left_word.substring(j + 1))){
result.set(0, left_word);
result.set(1, current);
return result;
}
}
}
current = "";
// 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)
for(int j = left_word.length() - 1; j >= 0; j--){
// Here, current string denotes stringreverse(left_word.substring(j + 1, len(left_word)))
// Check if current string is present in words or not
current = current + left_word.charAt(j);
if(count.containsKey(current)){
// Handles that case so that same string itself doesn't get picked
// up as other string in pair to form a palindrome
if(current.equals(left_word)){
if(count.get(current) > 1){
result.set(0, current);
result.set(1, left_word);
return result;
}
}
// Check if left_word.substring(0, j) is a palindrome or not
else if(isPalindrome(left_word.substring(0, j))){
result.set(0, current);
result.set(1, left_word);
return result;
}
}
}
}
return result;
}
// Check if string str is palindrome or not
static boolean isPalindrome(String str) {
int l = 0;
int n = str.length();
while(l < n - l){
if(str.charAt(l) != str.charAt(n - 1 - l)){
return false;
}
l++;
}
return true;
}
We hope that these solutions to join words to make a palindrome problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.
If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.
Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.
We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:
To learn more, register for the FREE webinar.
.png)
