https://leetcode.com/problems/palindrome-partitioning

First thing we need to see when we look at problem description, that n is pretty small, no more than 15, and it is done for reason: we will see in our complexity analysis why. Let us use function find_all_palindromes, where:

  1. s is input string, imagine abacc.
  2. Output is lengths of biggest palindromes for each of the 2n-1 possible middles. Why there is 2n-1? Because it can be either letter or in between letters.
  3. Here I use very simple way to find all palindromes: just consider every possible substring, there will be O(n^2) of them and check in O(n) if it is palindrome. Total complexity of this step is O(n^3), but we do not care here: complexity of the next step will be much bigger.

Now, let us dp[i+1] be solution for s[:i]. How we can find dp[i+1]? We need to iterate over all k in range (0, N): possible starts of last palindrome and check if B[2*i-k+1] >= k: this condition means that s[i-k: i+1] is palindrome: so now we just iterate over all solutions for dp[i-k] and add this string to the end of solutions. Why I prefer here dp solution, not backtracking, because it is more universal and you can solve 132. Palindrome Partitioning II just changing code a bit.

Comlexity: as we discussed, complexity of finding all palindromes is O(n^3). Now, imagine we have string aaa...aa with length n. Then there will be exactly 2^(n-1) ways to split this string in palindromes: we can cut it in any of n-1 places. So, there will be O(2^n* n) time and space to keep solution for s. Also we keep solution for all prefixes of s, but we have O(2^n * n + 2^(n-1)*(n-1) + ...) which is still O(2^n * n). Space complexity is the same: we need this amount of memory just to keep answer.

Remark I ran this code 6 months ago and it was around 60-70ms, now it is 600-700ms, this means, that leetcode added new tests and histogram is not relevant at the moment. Do not be discouraged when you see something like faster than 10%, it is not true.

Remark2 Note again, that find_all_palindromes(s) has complexity O(n^3) here, and there is O(n^2) and even O(n) algorithms for this. But if you change this part, difference will be negligible: you can try and will see.

class Solution:
    def partition(self, s):
        def find_all_palindromes(s):
            B = [0] * (2*n)
            for i, j in combinations_with_replacement(range(n), 2):
                if s[i:j+1] == s[i:j+1][::-1]:
                    B[i+j+1] = max(B[i+j+1], j-i+1)
            return B
        
        n = len(s)
        B = find_all_palindromes(s)
        
        dp = [[] for _ in range(n+1)]
        dp[0] = [[]]
        for i in range(0, n):
            for k in range(0, i+1):
                if B[2*i-k+1] >= k:
                    for elem in dp[i-k]:
                        dp[i + 1].append(elem  + [s[i-k:i+1]])

        return dp[-1]

If you like the solution, you can upvote it on leetcode discussion section: Problem 0131