 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:

## Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve. Hosted By
Ryan Valles
Founder, Interview Kickstart Accelerate your Interview prep with Tier-1 tech instructors 360° courses that have helped 14,000+ tech professionals 100% money-back guarantee*

All Posts