> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/strings/32.-palindrome-pairs.md).

# 30. Palindrome Pairs

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

```
Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]
```

**Example 2:**

```
Input: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]
```

**Example 3:**

```
Input: words = ["a",""]
Output: [[0,1],[1,0]]
```

## Solution: 

**Approach:** \
**Find the possible palindromic substring** \
**Find the reverse of left part to make it palindrome**

```cpp
class Solution
{
public:
    bool isPalin(string s)
    {

        int i = 0;
        int j = s.length() - 1;

        while (i <= j)
        {
            if (s[i] != s[j])
            {
                return false;
            }
            i++;
            j--;
        }

        return true;
    }

    vector<vector<int>> palindromePairs(vector<string> &words)
    {

        unordered_map<string, int> m;
        vector<vector<int>> res;

        for (int i = 0; i < words.size(); i++)
        {
            m[words[i]] = i;
        }

        if (m.find("") != m.end())
        {
            int idx = m[""];

            for (int i = 0; i < words.size(); i++)
            {
                if (words[i] == "")
                {
                    continue;
                }

                string s = words[i];
                reverse(s.begin(), s.end());
                if (s == words[i])
                {
                    res.push_back({i, idx});
                    res.push_back({idx, i});
                }
            }
        }

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

            int n = words[i].length();

            for (int k = 1; k <= n; k++)
            {
                string ls = words[i].substr(0, k);
                string rs = words[i].substr(k, n - k);

                string rrev = rs;
                reverse(rrev.begin(), rrev.end());

                string lrev = ls;
                reverse(lrev.begin(), lrev.end());

                if (isPalin(ls) && m.find(rrev) != m.end() && rs != "" && m[rrev] != i)
                {

                    res.push_back({m[rrev], i});
                }

                if (isPalin(rs) && m.find(lrev) != m.end() && m[lrev] != i)
                {

                    res.push_back({i, m[lrev]});
                }
            }
        }

        return res;
    }
};
```

**Time Complexity: O(n \* k^2)**