MediumStringDynamic ProgrammingBacktrackingUpdated Sep 2026

131. Palindrome Partitioning

Asked at Salesforce, Visa

Difficulty

Medium

Time

O(n * 2^n)

Space

O(n^2)

Pattern

String

Companies

2

Problem

You are given a string s. You must cut s into one or more pieces so that the pieces, read in order, spell out s again. Every piece must be a palindrome — a string that reads the same forwards and backwards.

Return all the different ways to cut s this way. Each way is a list of the pieces in order. The order of the ways in your answer does not matter.

A cut can be placed between any two characters, or not at all. Two ways count as different if the pieces are different, so ["a","a","b"] and ["aa","b"] are two separate answers.

Every piece must be a palindrome

saabaab012Cut after every character: "a", "a", "b" — all threeare palindromes, so this is a valid answer.saabaab012Cut only after index 1: "aa" and "b" — both arepalindromes, so this is the second valid answer.
For s = "aab" we try cut positions and keep only the cuts where all pieces read the same both ways.

Constraints

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

Examples

Example 1
Inputs = "aab"
Output[["a","a","b"],["aa","b"]]
WhyCutting after every character gives "a", "a", "b" — each piece is a palindrome. Cutting only after the second character gives "aa" and "b" — both are palindromes too. The cut "a" | "ab" fails because "ab" is not a palindrome, and no other cut works.
Example 2
Inputs = "a"
Output[["a"]]
WhyThere is only one character, so the only possible partition is the whole string as a single piece, and a one-character string is always a palindrome.

Asked At

2 companies
CompanyDifficulty
SalesforceMediumView all Salesforce questions →
VisaMediumView all Visa questions →

How to Think About It

1

Brute force: generate all possible partitions (2^(n-1) ways to cut) and check each substring for being a palindrome.

2

Use backtracking: at each position, try all possible ending points for the current substring.

3

If the current substring s[i..j] is a palindrome, add it to the current path and recurse on s[j+1:].

4

Precompute palindrome validity with DP: isPal[i][j] is true if s[i..j] is a palindrome.

5

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.

Backtracking with a palindrome table

isPal012012TTFTFTisPal[0][1] is true because "aa" is a palindrome;isPal[0][2] is false because "aab" is not.start = 0, path = []try "a" → recurse at 1try "aa" → recurse at 2From index 0 we can only take "a" or "aa", since those arethe palindromic prefixes."a" → "a" → "b" ✓"aa" → "b" ✓start == n → record pathBoth branches reach the end of the string, so both paths areadded to the result.isPal[i][j] = s[i]==s[j] and (j-i<2 or isPal[i+1][j-1])if isPal[start][end]: take s[start..end], recurse(end+1)
First fill isPal[i][j] for all substrings, then walk left to right and only extend with pieces that are palindromes.
ComplexityTime O(n * 2^n)Space O(n^2)The O(n^2) part builds the palindrome table, and the O(n * 2^n) part comes from exploring up to 2^(n-1) cut patterns and copying each answer of length up to n.

What Trips People Up in Real Interviews

1

Clarify: all partitions must be returned, not just one — the output is a list of lists.

2

Edge case: single character string — the only partition is [[s]].

3

Edge case: entire string is a palindrome — [[s]] is one valid partition along with all finer splits.

4

The palindrome precomputation (DP or expand-around-center) is a common subproblem worth discussing.

5

Explain the backtracking tree clearly: each level represents a partition boundary, each branch represents a possible substring.

Solution Code

O(n * 2^n) time
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 result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n * 2^n) time and O(n^2) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Palindrome Partitioning?

Palindrome Partitioning is asked at Salesforce, Visa. 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.