<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:
        '''
        * split s into 3 palindromic substrings, which when concatenated returns original string s..
        * if it's possible, return True 
        ====
        for each char in c, I need to know where it's 'mirror' element is.. 
        *** optimized approach: incomplete.. 
        ====
        3 <= s.length <= 2000, it's at most 2000 chars.. and it's always 3 parts.. 
        naive approach: 
            * make a first cut such that I can form other two parts as non empty with the remaining elements..
            * if first part (0, first_cut) is a palindrome.. then make a second cut somewhere after the first cut such that third part can be formed as non empty part with remaining elements.. 
            * when making the second cut... if (first_cut + 1, second_cut) (the second part) and (second_cut + 1, len(s)-1) (the third cut) are also palindromes.. then I found a 'true' case

            * if I never hit a true case, then just return False

        '''


        ### betting on O(+**2) since 3 <= s.length <= 2000 => naive works!
        @cache
        def check(l, r): 
            if l >= r: # pointing the same index 
                return True 
            
            if s[l] != s[r]: return False

            return check(l + 1, r - 1)


        for first_cut in range(len(s)-2): # the other two cuts should be non empty.. 
            if check(0, first_cut): # first part is okay.. 
                for second_cut in range(first_cut + 1, len(s)-1): # last part should be non empty.. 
                    if check(first_cut + 1, second_cut) and check(second_cut + 1, len(s)-1): 
                        return True 
        return False




        ### incomplete: optimized version: ### need to think of a way to cache all palindromic substrings from an index.. 
        # half_len = len(s) // 2

        # mirror_char = collections.defaultdict(set)

        # for fhalf_c, shalf_c in zip(s[:half_len + 1], s[half_len:])
        #     if fhalf_c == shalf_c: 
        #         mirrot_char[fhalf_c].add(shalf_c)


        # def helper(idx, rem): 
        #     if idx >= len(s): # exhausted
        #         if rem == 0: # formed all 3 pals 
        #             return True # good case
        #         return False # bad case

        #     if rem < 0: return False # over forming 

        #     isOk = False

        #     for cut in mirror_char[s[idx]]: 
        #         isOk |= helper(cut + 1, rem - 1) # try to form rem parts after this cut.. 
        #     return isOk


        # return helper(0, 3) # start from idx 0 and make 3 parts.. 
2638