<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):
        hashValue = (prefixHash[r + 1] - prefixHash[l] * power[r - l + 1]) % mod
        return (hashValue + mod) % mod

    def isPalindrom(self, l, r, p1, p2, power, powerRev, n):
        half = (r - l + 1) // 2 - 1
        ll = l 
        lr = l + half
        rl = n - r - 1 
        rr = n - (r - half) - 1
        if self.getSubstringHash(p1, power, ll, lr) == self.getSubstringHash(p2, powerRev, rl, rr):
            return True
        return False

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

        for i in range(1, n - 1):
            for j in range(i + 1, n):
                if (self.isPalindrom(0, i - 1, prefixHash, prefixHashRev, power, powerRev, n) and
                    self.isPalindrom(i, j - 1, prefixHash, prefixHashRev, power, powerRev, n) and
                    self.isPalindrom(j, n - 1, prefixHash, prefixHashRev, power, powerRev, n)):
                    return True

        return False
17100