<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>

class Solution:
    def checkPartitioning(self, s: str) -> bool:
        # O(N^3)
        # manacher over s to find first substring
        # for each ending of first substring, manacher over the rest to find the second substring
        # for each ending of the second substring, check if the rest is palindrome

        # O(N^2)
        # figure out which pairs of indices are palindromes, ... DP of some sort??
        # rules:
        #   if i:j is a palindrome, i+1:j-1 is as well
        #.  otherwise, check s[i] == s[j]
        # check if there is a palindrome at (i, j) such that (0, i) and (j, n) are palindromes as well

        n = len(s)
        mem = [[-1]*n for _ in range(n)]

        def is_pal(i, j):
            if i >= j:
                return True
            if mem[i][j] != -1:
                return bool(mem[i][j])

            inner = is_pal(i + 1, j - 1)
            if inner and s[i] == s[j]:
                mem[i][j] = 1
                return True

            is_pal(i + 1, j)
            is_pal(i, j - 1)

            mem[i][j] = 0
            return False

        for i in range(len(s)):
            for j in range(1, i):
                if is_pal(0, j - 1) and is_pal(j, i - 1) and is_pal(i, len(s) - 1):
                    return True

        return False

5106