<p>You are given a <strong>0-indexed</strong> array of <strong>unique</strong> strings <code>words</code>.</p>

<p>A <strong>palindrome pair</strong> is a pair of integers <code>(i, j)</code> such that:</p>

<ul>
	<li><code>0 &lt;= i, j &lt; words.length</code>,</li>
	<li><code>i != j</code>, and</li>
	<li><code>words[i] + words[j]</code> (the concatenation of the two strings) is a <span data-keyword="palindrome-string">palindrome</span>.</li>
</ul>

<p>Return <em>an array of all the <strong>palindrome pairs</strong> of </em><code>words</code>.</p>

<p>You must write an algorithm with&nbsp;<code>O(sum of words[i].length)</code>&nbsp;runtime complexity.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;abcd&quot;,&quot;dcba&quot;,&quot;lls&quot;,&quot;s&quot;,&quot;sssll&quot;]
<strong>Output:</strong> [[0,1],[1,0],[3,2],[2,4]]
<strong>Explanation:</strong> The palindromes are [&quot;abcddcba&quot;,&quot;dcbaabcd&quot;,&quot;slls&quot;,&quot;llssssll&quot;]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;bat&quot;,&quot;tab&quot;,&quot;cat&quot;]
<strong>Output:</strong> [[0,1],[1,0]]
<strong>Explanation:</strong> The palindromes are [&quot;battab&quot;,&quot;tabbat&quot;]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;a&quot;,&quot;&quot;]
<strong>Output:</strong> [[0,1],[1,0]]
<strong>Explanation:</strong> The palindromes are [&quot;a&quot;,&quot;a&quot;]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= words.length &lt;= 5000</code></li>
	<li><code>0 &lt;= words[i].length &lt;= 300</code></li>
	<li><code>words[i]</code> consists of lowercase English letters.</li>
</ul>

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>> res;
        unordered_map<string, int> wordToIndex;
        set<int> wordSize;

        int len = words.size();
        for(int i = 0; i < len; ++i) {
            wordToIndex[words[i]] = i;
            wordSize.insert(words[i].size());
        }

        for(int i = 0; i < len; ++i) {
            string copy = words[i];

            reverse(copy.begin(), copy.end());

            // when copy is processed later, reversed index pair will be added
            if(wordToIndex.count(copy) && wordToIndex[copy] != i) {
                res.push_back({i, wordToIndex[copy]});
            }

            int len = copy.size();
            auto end = wordSize.find(len);
            for(auto it = wordSize.begin(); it != end; ++it) {
                int size = *it;

                //check just concatenate
                //[abcd, cba], size = 3, len = 4
                // copy = dcba
      
                string toMatch = copy.substr(len-size); // toMatch = cba
                if(isPalin(copy, 0, len-size-1) && wordToIndex.count(toMatch)) {
                    res.push_back({i, wordToIndex[toMatch]});
                }

                //check reverse concatenate
                //[dcba, abc], size = 3, len = 4
                // copy = abcd
                toMatch = copy.substr(0, size); // toMatch = abc
                if(isPalin(copy, size, len-1) && wordToIndex.count(toMatch)) {
                    res.push_back({wordToIndex[toMatch], i});
                }
            }
        }

        return res;
    }

    bool isPalin(const string &str, int start, int end) {
        while(start < end) {
            if(str[start] != str[end])
                return false;
            ++start;
            --end;
        }
        return true;
    }
};
242888