Palindrome Partitioning
Asked at Salesforce
Problem
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitionings of s. A palindrome is a string that reads the same forward and backward.
Asked At
| Company | Difficulty | |
|---|---|---|
| Salesforce | MEDIUM | View all Salesforce questions → |
How to Think About It
Brute force: generate all possible partitions (2^(n-1) ways to cut) and check each substring for being a palindrome.
Use backtracking: at each position, try all possible ending points for the current substring.
If the current substring s[i..j] is a palindrome, add it to the current path and recurse on s[j+1:].
Precompute palindrome validity with DP: isPal[i][j] is true if s[i..j] is a palindrome.
Base case: when the current index reaches the end of the string, record the current partition as a valid result.
Optimal Approach
Precompute a 2D boolean array isPal where isPal[i][j] indicates whether s[i..j] is a palindrome using bottom-up DP. Then use backtracking starting from index 0: try every possible end index j, check isPal[i][j], and if true, include s[i..j] in the current partition and recurse from j+1. When the index reaches the end of the string, record the partition. Time complexity is O(n * 2^n) in the worst case due to the number of partitions, with O(n^2) preprocessing.
What Trips People Up in Real Interviews
Clarify: all partitions must be returned, not just one — the output is a list of lists.
Edge case: single character string — the only partition is [[s]].
Edge case: entire string is a palindrome — [[s]] is one valid partition along with all finer splits.
The palindrome precomputation (DP or expand-around-center) is a common subproblem worth discussing.
Explain the backtracking tree clearly: each level represents a partition boundary, each branch represents a possible substring.
Solution Code
def partition(s):
n = len(s)
isPal = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
isPal[i][j] = s[i] == s[j] and (j - i < 2 or isPal[i + 1][j - 1])
result = []
def backtrack(start, path):
if start == n:
result.append(path[:])
return
for end in range(start, n):
if isPal[start][end]:
path.append(s[start:end + 1])
backtrack(end + 1, path)
path.pop()
backtrack(0, [])
return resultFrequently Asked Questions
What is the Palindrome Partitioning problem?
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitionings of s. A palindrome is a string that reads the same forward and backward.
How do you solve Palindrome Partitioning?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Palindrome Partitioning?
Palindrome Partitioning is asked at Salesforce. It is a medium difficulty problem.
What are common mistakes on Palindrome Partitioning?
- Clarify: all partitions must be returned, not just one — the output is a list of lists.
- Edge case: single character string — the only partition is [[s]].
- Edge case: entire string is a palindrome — [[s]] is one valid partition along with all finer splits.
- The palindrome precomputation (DP or expand-around-center) is a common subproblem worth discussing.
- Explain the backtracking tree clearly: each level represents a partition boundary, each branch represents a possible substring.