<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>

"""
Naive:
- Try every partitioning combination and check if they are all palindromes
    - Use two pointer: 
Time: O(n! * n)

- Iterate throught the string
- At each index, try to expand the palindromes => for each palindrome that I found => concat them to all possible previous partition
aab
{
    1: [a],
    2: [a, a], [aa]
    3: [a, a, b], [aa, b]
}

aabbb
combs = {
    1: [[a]]
    2: [[aa], [a, a]]
    3: [[aa, b], [a, a, b]]
    4: [[aa, bb], [a, a, bb], [aa, b, b], [a, a, b, b]]
    5: [[aa, bbb], [a, a, bbb], [aa, b, bb], [a, a, b, bb], [aa, bb, b], [a, a, bb, b], [aa, b, b, b], [a, a, b, b, b]]
}

i = 0
0,0
0,1

i = 1
1,1 => [a,a]
1, 2

i = 2
2, 2
2, 3

i = 3
3, 3 => 2, 4
3, 4 => 2, 5

i = 4
4, 4
4, 5

"""

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        combs = defaultdict(list)
        
        def helper(left, right):
            nonlocal s
            nonlocal combs

            while left >= 0 and right < len(s):
                if s[left] != s[right]:
                    break
                
                # add new combination
                prev_combs = combs[left]
                
                new_combs = []
                substr = s[left: right+1]
                for comb in prev_combs:
                    new_comb = comb.copy()
                    new_comb.append(substr)
                    new_combs.append(new_comb)
                if not new_combs:
                    new_combs = [[substr]]
                combs[right+1].extend(new_combs)
                # expand
                left -= 1
                right += 1
            
            return

        
        for i in range(len(s)):
            # odd palindrome
            helper(i, i)
            # even palindrome
            helper(i, i+1)
        
        return combs[len(s)]

32478