Palindrome Partitioning

Problem Statement

Given a string s, split s into substrings where every substring is a palindrome. Return all possible lists of palindromic substrings.

You may return the solution in any order.

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a"
Output: [["a"]]

Constraints:

  • 1 <= s.length <= 20
  • s contains only lowercase English letters.

You should aim for a solution with O(n \cdot (2^n)) time and O(n) space, where n is the length of the input string.

You should aim for a solution with O(n \cdot (2^n)) time and O(n) space, where n is the length of the input string.

Hint 1

For a given string there are 2^n possible partitions because at each index we have two decisions: we can either partition and start a new string, or continue without partitioning. Can you think of an algorithm to recursively traverse all combinations?

Hint 2

We can use backtracking to recursively traverse the string with indices j (start of the current substring) and i (current iterating index). At each step, we either skip partitioning at the current index or, if the substring from j to i is a palindrome, make a partition, update j = i + 1, and start a new substring. The base condition to stop the recursion is when j reaches the end of the string. How do you implement this?

Hint 3

We start with j = 0, i = 0 and a temporary list which stores the substrings from the partitions. Then we recursively iterate the string with the index i. At each step we apply the 2 decisions accordingly. At the base condition of the recursive path, we make a copy of the current partition list and add it to the result.

Solution

Backtracking (Pick / Not Pick)

def partition(s: str) -> list[list[str]]:
res, part = [], []
def dfs(j, i):
if i >= len(s):
if i == j:
res.append(part.copy())
return
if is_palindrome(s, j, i):
part.append(s[j : i + 1])
dfs(i + 1, i + 1)
part.pop()
dfs(j, i + 1)
def is_palindrome(s, l, r):
while l < r:
if s[l] != s[r]:
return False
l, r = l + 1, r - 1
return True
dfs(0, 0)
return res

Time complexity: O(n \cdot 2 ^ n) Space complexity: O(n)

Backtracking

def partition(s: str) -> list[list[str]]:
res, part = [], []
def dfs(i):
if i >= len(s):
res.append(part.copy())
return
for j in range(i, len(s)):
if is_palindrome(s, i, j):
part.append(s[i : j + 1])
dfs(j + 1)
part.pop()
def is_palindrome(s, l, r):
while l < r:
if s[l] != s[r]:
return False
l, r = l + 1, r - 1
return True
dfs(0)
return res

Time complexity: O(n \cdot 2 ^ n) Space complexity: O(n)

Backtracking (DP)

def partition(s: str) -> list[list[str]]:
n = len(s)
dp = [[False] * n for _ in range(n)]
for l in range(1, n + 1):
for i in range(n - l + 1):
dp[i][i + l - 1] = (s[i] == s[i + l - 1] and
(i + 1 > (i + l - 2) or
dp[i + 1][i + l - 2]))
res, part = [], []
def dfs(i):
if i >= len(s):
res.append(part.copy())
return
for j in range(i, len(s)):
if dp[i][j]:
part.append(s[i : j + 1])
dfs(j + 1)
part.pop()
dfs(0)
return res

Time complexity: O(n \cdot 2 ^ n) Space complexity: O(n ^ 2)

Recursion

def partition(s: str) -> list[list[str]]:
n = len(s)
dp = [[False] * n for _ in range(n)]
for l in range(1, n + 1):
for i in range(n - l + 1):
dp[i][i + l - 1] = (s[i] == s[i + l - 1] and
(i + 1 > (i + l - 2) or
dp[i + 1][i + l - 2]))
def dfs(i):
if i >= n:
return [[]]
ret = []
for j in range(i, n):
if dp[i][j]:
nxt = dfs(j + 1)
for part in nxt:
cur = [s[i : j + 1]] + part
ret.append(cur)
return ret
return dfs(0)

Time complexity: O(n \cdot 2 ^ n) Space complexity: O(n ^ 2)