<p>Given a string <code>s</code>, return <code>true</code> <em>if it is possible to split the string</em> <code>s</code> <em>into three <strong>non-empty</strong> palindromic substrings. Otherwise, return </em><code>false</code>.​​​​​</p>

<p>A string is said to be palindrome if it the same string when reversed.</p>

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

<pre>
<strong>Input:</strong> s = &quot;abcbdd&quot;
<strong>Output:</strong> true
<strong>Explanation: </strong>&quot;abcbdd&quot; = &quot;a&quot; + &quot;bcb&quot; + &quot;dd&quot;, and all three substrings are palindromes.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;bcbddxy&quot;
<strong>Output:</strong> false
<strong>Explanation: </strong>s cannot be split into 3 palindromes.
</pre>

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

<ul>
	<li><code>3 &lt;= s.length &lt;= 2000</code></li>
	<li><code>s</code>​​​​​​ consists only of lowercase English letters.</li>
</ul>

import itertools

class Solution:
    def checkPartitioning(self, s: str) -> bool:
        # need 2 indices start, end such that s[:start], s[start:end], s[end:] all non-empty palindromes
        # brute force, if we check all pairs, substrings -> O(N^3) algorithm
        # if we first locate all palindromes we can do this quicker
        # start from each centre and add left, right characters each time and check for being a palindrome
        # now we check all pairs, can check if this defines 3 palindromes in O(1) -> O(N^2) time/space algorithm

        # edge cases:
        #   - len(s) < 3
        #   - aaaa....aaaaa (will take >> N^2 time / space)
        #.  - 

        # find all palindromes
        palindrome_indices = set() # start inclusive, end exclusive

        for start in range(len(s)):
            for end in (start, start + 1): # odd, even length resp.
                i, j = start, end
                while i >= 0 and j < len(s):
                    if s[i] == s[j]:
                        palindrome_indices.add((i, j + 1))
                    else:
                        break
                    i -= 1
                    j += 1

        
        # check all end-points
        for idx1, idx2 in itertools.combinations(range(1, len(s)), 2):
            if idx1 > idx2:
                idx1, idx2 = idx2, idx1
            if (
                ((0, idx1) in palindrome_indices)
                and ((idx1, idx2) in palindrome_indices)
                and ((idx2, len(s)) in palindrome_indices)
                ):
                return True
        return False

2821