<p>Given a string <code>s</code>, partition <code>s</code> such that every <span data-keyword="substring-nonempty">substring</span> of the partition is a <span data-keyword="palindrome-string"><strong>palindrome</strong></span>. Return <em>all possible palindrome partitioning of </em><code>s</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> s = "aab"
<strong>Output:</strong> [["a","a","b"],["aa","b"]]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = "a"
<strong>Output:</strong> [["a"]]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 16</code></li>
	<li><code>s</code> contains only lowercase English letters.</li>
</ul>

from collections import defaultdict
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        """
        idea: build a list of lists, L, where L[i][j] = j'th partition in the i'th partitioning
        starting from x=0, and y=1, set i = 0 and j = 0.
        while s[x:y] is a palindrome, append the substring 
        s[x:y] to L[i] and increment i.
        when while condition fails, increment j.
        repeat while loop above except picking up where we left off in each partitioning
        i.e. start at x=1 and y=2 if we left off at y=1 (need a mapping of i -> x).
        """
        L = []
        partition_to_offset = defaultdict(int)
        n = len(s)
        x = 0
        y = 1
        i = 0
        j = 0
        #initialize list of lists
        for y in range(x+1,n+1):
            if self.isPalindrome(s[x:y]):
                L.append([s[x:y]])
                partition_to_offset[i] = y
                i+=1
        while min(partition_to_offset.values()) < n:
            l = len(L)
            for i in range(l):
                partitioning = L[i].copy()
                x = partition_to_offset[i]
                y = x+1
                if y<=n and x<n:
                    L[i].append(s[x:y])
                    partition_to_offset[i] = y
                y+=1
                for y in range(x+2,n+1):
                    if self.isPalindrome(s[x:y]):
                        L.append(partitioning + [s[x:y]])
                        partition_to_offset[len(L)-1] = y
                        y+=1
            
        return L
                
    def isPalindrome(self, s:str) -> bool:
        n = len(s)
        for k in range(n//2):
            if s[k] != s[n-k-1]:
                return False
        return True
        
30033