<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:
#         n = len(s)
#         def checker(i,j):
#             while i < j:
#                 if s[i] != s[j]:
#                     return False
#                 i += 1
#                 j -= 1
#             return True

#         memo = {}
#         def solver(index,count):
#             if index == n:
#                 if count == 3:
#                     return True
#                 return False
            
#             if (index,count) in memo:
#                 return memo[(index,count)]

#             for i in range(index,len(s)):
#                 if checker(index,i):
#                     if not solver(i+1,count+1):
#                         continue
#                     memo[(index,count)] = True
#                     return memo[(index,count)]
#             memo[(index,count)] = False
#             return memo[(index,count)]

#         return solver(0,0)


class Solution:
    def checkPartitioning(self, s: str) -> bool:
        n = len(s)
        
        # Precompute palindrome table
        isPalindrome = [[False] * n for _ in range(n)]
        for i in range(n):
            isPalindrome[i][i] = True
        for i in range(n-1):
            isPalindrome[i][i+1] = (s[i] == s[i+1])
        for length in range(3, n+1):
            for i in range(n-length+1):
                j = i + length - 1
                isPalindrome[i][j] = (s[i] == s[j]) and isPalindrome[i+1][j-1]
        
        # DP table
        dp = [[False for _ in range(4)] for _ in range(n+1)]
        dp[n][3] = True
        
        for index in range(n-1, -1, -1):
            for count in range(2, -1, -1):
                for i in range(index, n):
                    if isPalindrome[index][i]:
                        if not dp[i+1][count+1]:
                            continue
                        dp[index][count] = True

        return dp[0][0]

2912