<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 computePrefixHash(self, s: str, p: int = 31, mod: int = 10**9 + 7):
        n = len(s)
        prefixHash = [0] * (n + 1)
        power = [1] * (n + 1)

        for i in range(1, n + 1):
            prefixHash[i] = (prefixHash[i - 1] * p + ord(s[i - 1])) % mod
            power[i] = (power[i - 1] * p) % mod

        return prefixHash, power

    def getSubstringHash(self, prefixHash, power, l, r, mod: int = 10**9 + 7):
        return (prefixHash[r + 1] - prefixHash[l] * power[r - l + 1] % mod + mod) % mod

    def isPalindrom(self, l, r, prefixHash, revHash, power, revPower, n):
        forwardHash = self.getSubstringHash(prefixHash, power, l, r)
        reverseHash = self.getSubstringHash(revHash, revPower, n - r - 1, n - l - 1)
        return forwardHash == reverseHash

    def checkPartitioning(self, s: str) -> bool:
        n = len(s)
        prefixHash, power = self.computePrefixHash(s)
        revHash, revPower = self.computePrefixHash(s[::-1])

        # Precompute palindromic prefixes and suffixes
        prefixPal = [False] * n
        suffixPal = [False] * n

        for i in range(n):
            if self.isPalindrom(0, i, prefixHash, revHash, power, revPower, n):
                prefixPal[i] = True
            if self.isPalindrom(i, n - 1, prefixHash, revHash, power, revPower, n):
                suffixPal[i] = True

        # Check the middle palindrome
        for i in range(n):
            if prefixPal[i]:
                for j in range(i + 1, n - 1):
                    if suffixPal[j + 1] and self.isPalindrom(i + 1, j, prefixHash, revHash, power, revPower, n):
                        return True

        return False



    

718