Framework Thinking - Neetcode 150 - Palindrome Partitioning
Here is solutions for Palindrome Partitioning.
1. Understand the problem
-
Given a string s, partition it such that every substring in the partition is a palindrome.
-
Return all possible palindrome partitionings of s.
-
Example: s = “aab”
[
["a","a","b"],
["aa","b"]
]
2. Clarify constraints, asks 4 - 5 questions including edge cases.
- Length of s?
- Typically: 1 ≤ len(s) ≤ 16 (small → exponential solutions are expected)
- Characters?
- Lowercase English letters only.
- Return order important?
- No, any valid order is accepted.
- What if the entire string is already a palindrome?
- Then one valid partition is [s].
- Edge Cases:
-
s = “a” → [[“a”]]
-
s = “” → Usually not tested, but would return [[]]
-
All same characters: “aaa” → many valid partitions
-
No palindrome longer than 1: “abc” → only single-character splits
3. Explore examples.
- Example 1:
s = "aab"
[["a","a","b"], ["aa","b"]]
- Example 2:
s = "aba"
[["a","b","a"], ["aba"]]
4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.
4.1. ✅ Solution 1: Naive Backtracking (Brute Force) - Time: O(N * 2^N), Space O(N * 2^N).
-
Idea:
-
Try every possible prefix.
-
If the prefix is a palindrome → recursively partition the rest.
-
Store valid partitions.
-
-
Time: O(N * 2^N).
-
Space: O(N * 2^N).
4.2. Solution 2: Backtracking + Memoized Palindrome Check (Optimized) - Time: O(N * 2^N), Space O(N * 2^N).
-
Pre-computed if dp[i][j] is palindrome, add s[i: j + 1]
-
Continue to backtrack the rest.
5. Implement solutions.
5.1. Backtracking - II - Time: O(N * 2^N), Space O(N * 2^N).
class Solution:
def partition(self, 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 self.isPali(s, i, j):
part.append(s[i : j + 1])
dfs(j + 1)
part.pop()
dfs(0)
return res
def isPali(self, s, l, r):
while l < r:
if s[l] != s[r]:
return False
l, r = l + 1, r - 1
return True
-
Idea: Because we always have 1-character is palindrom, so we check a a b or aa b => And in this case aab, we skip it. -
Time: O(N * 2^N)
- Space: O(N * 2^N).
5.2. Backtracking + DP - Time: O(N * 2^N), Space O(N * 2^N).
class Solution:
def partition(self, 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
Idea: At char i, pick or reject char[i] is 2 choices => 2^N.
-
Time: O(N * 2^N)
-
Space: O(N * 2^N).
5.3. Recursion, Backtracking with return - Time: O(N * 2^N), Space O(N * 2^N).
class Solution:
def partition(self, 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: O(N * 2^N)
-
Space: O(N * 2^N).
6. Dry run testcases.
dfs(0)
├── "a" → dfs(1)
│ ├── "a" → dfs(2)
│ │ ├── "a" → dfs(3)
│ │ │ └── "a" → dfs(4) ✅ ["a","a","a","a"]
│ │ └── "aa" → dfs(4) ✅ ["a","a","aa"]
│ ├── "aa" → dfs(3)
│ │ └── "a" → dfs(4) ✅ ["a","aa","a"]
│ └── "aaa" → dfs(4) ✅ ["a","aaa"]
│
├── "aa" → dfs(2)
│ ├── "a" → dfs(3)
│ │ └── "a" → dfs(4) ✅ ["aa","a","a"]
│ └── "aa" → dfs(4) ✅ ["aa","aa"]
│
├── "aaa" → dfs(3)
│ └── "a" → dfs(4) ✅ ["aaa","a"]
│
└── "aaaa" → dfs(4) ✅ ["aaaa"]