[Uber] Palindrome Pairs

Problem: Given a list of unique words, return all the pairs of the distinct indices (i, j) in the given list, so that the concatenation of the two words words[i] + words[j] is a palindrome.

Example:

Input: words = ["abc","cba","nish","h","hhsin"]
Output: [[0,1],[1,0],[2,4]]
Explanation: The palindromes are ["abccba","cbaabc","nishhhsin"]

Approach: One brute-force approach would be to consider each pair one by one. If any pair forms a palindrome after concatenating them than add that pair to result. This will work but will take O(n^2 * k) time where n is the number of words and k is the maximum length of the pair checked for palindrome. 

Let's go to another approach which is much better in case number of words are way more than the average length of words (more real world scenario). Here is the algorithm:

• If you see we need to return the list of pair of indices so it is intuitive that we maintain a hash with key as word and value as it's index in the input list.
• Now we will iterate through each word of input:
• We will iterate through every 2 substrings possible for that word:
• SubStr1 = word[0...i]
• SubStr2 = word[i + 1....length of word] (For i = 0 to length of word)
• For each of these substrings we will check:
• IF SubStr1 is palindrome (means SubStr1 can be pivot)
• IF hash contains the reverse of SubStr2 AND hash[SubStr2] is not current index
• We will add hash[SubStr2] and current index to result
• IF  SubStr2 is palindrome (means SubStr2 can be pivot)  AND length of SubStr2 > 0 (To avoid duplicate)
• IF hash contains the reverse of SubStr1 AND hash[SubStr1] is not current index
• We will add current index and hash[SubStr1] to result

That's all!

Implementation in C#:

        public IList<IList<int>> PalindromePairs(string[] words)

        {

            List<IList<int>> result = new List<IList<int>>();

            if (words?.Length <= 1)

            {

                return result;

            }

            Dictionary<string, int> wordToIndexMap = new Dictionary<string, int>();

            for (int i = 0; i < words.Length; ++i)

            {

                wordToIndexMap.Add(words[i], i);

            }

            for (int i = 0; i < words.Length; ++i)

            {

                for (int j = 0; j <= words[i].Length; ++j)

                {

                    string subStr1 = words[i].Substring(0, j);

                    string subStr2 = words[i].Substring(j);

                    if (this.IsPalindrome(subStr1, 0, subStr1.Length - 1))

                    {

                        string subStr2Rev = subStr2.Reverse();

                        if (wordToIndexMap.ContainsKey(subStr2Rev) && wordToIndexMap[subStr2Rev] != i)

                        {

                            result.Add(new List<int> { wordToIndexMap[subStr2Rev], i });

                        }

                    }

                    if (subStr2.Length > 0 && this.IsPalindrome(subStr2, 0, subStr2.Length - 1))

                    {

                        string subStr1Rev = subStr1.Reverse();

                        if (wordToIndexMap.ContainsKey(subStr1Rev) && wordToIndexMap[subStr1Rev] != i)

                        {

                            result.Add(new List<int> { i, wordToIndexMap[subStr1Rev] });

                        }

                    }

                }

            }

            return result;

        }

        

        // start index and end index are not necessary as in this case it will always be 0 and length - 1

        private bool IsPalindrome(string s, int startIndex, int endIndex)

        {

            while(startIndex < endIndex)

            {

                if (s[startIndex++] != s[endIndex--])

                {

                    return false;

                }

            }

            return true;

        }

        

        // To use this extension as is, you need to put in a static class

        public static string Reverse(this string str)

        {

            char[] tempCharArr = str.ToCharArray();

            Array.Reverse(tempCharArr);

            return new string(tempCharArr);

        }

Complexity: O(n * k ^ 2)