Register for our webinar

### How to Nail your next Technical Interview

1 hour
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

## You may be missing out on a 66.5% salary hike*

### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.

## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.

# 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 `x`th word in `words`. Task is to find out if there exists some `y`th 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 `x`th word in `words`. Task is to find out if there exists some `y`th 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:

### Try yourself in the Editor

Note: Input and Output will already be taken care of.

# 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 `x`th word in `words`. Task is to find out if there exists some `y`th 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 `x`th word in `words`. Task is to find out if there exists some `y`th 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: