Palindrome Partitioning

Given a string s, split it into consecutive pieces so that every piece reads the same forwards and backwards — a palindrome. Return all such partitionings.

A partition keeps the original left-to-right order of s; you only decide where to cut. Because every single character is itself a palindrome, at least one valid partition always exists.

Return the list of partitions in any order; within a partition the pieces appear in the order they occur in s.

Hints

· Stuck? Reveal one nudge at a time.

Every single letter is already a palindrome, so you can always fall back to cutting between every character — what extra freedom do longer palindromic pieces buy you?

Fix the first piece: try every prefix, and whenever that prefix is a palindrome, solve the very same problem on the remaining suffix.

The palindrome test keeps repeating on the same substrings — cache all answers in a boolean table pal[i][j] built from the inside out so each check is O(1).

Common doubts

Yes. A partition only chooses where to cut; it never rearranges characters, so the pieces read left to right exactly as in s.

Yes. Every single character is a palindrome, so the all-singletons partition is always one valid answer.

The number of partitions can grow like 2^(n-1). An exponential-sized answer is unavoidable, so the input is kept tiny.

Interview follow-ups

· What an interviewer asks next.

That is Palindrome Partitioning II — drop the enumeration and run a 1-D DP over cut positions on top of the same palindrome table.

Do a DP that sums, over each palindromic prefix, the count for the remaining suffix — this avoids materializing the exponential output.

Fun facts

The palindrome table pal[i][j] is the exact same trick that powers Longest Palindromic Substring.
A string of n identical characters has 2^(n-1) palindrome partitions — the same count as the compositions of the integer n.

Asked at

AmazonGoogleMicrosoftMetaBloomberg

Frequently Sometimes Occasionally

Example 1

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
"a","a","b" are each palindromes, and so are "aa","b".

Example 2

Input: s = "a"
Output: [["a"]]
A single character is already a palindrome.

Constraints

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

Palindrome Partitioning is the problem that teaches backtracking paired with a reusable check: enumerate every way to slice a string into palindromes, and learn to stop redoing the same work.

Prerequisites

Before you start

· Concepts used directly in the solution.

Recursion & backtracking. Build a partition one piece at a time, then undo the last choice to explore the next.

Two-pointer palindrome check. Compare characters from both ends moving inward to test whether a substring is a palindrome.

Interval DP. Cache whether s[i..j] is a palindrome using the already-known answer for the smaller inside s[i+1..j-1].

Understand the problem

You are given a string s. A partition cuts s into consecutive, non-empty pieces with order preserved. A partition is valid when every piece is a palindrome. Return every valid partition.

Worked example — s = "aab"

s = aab

cut a|a|b   -> [a, a, b]    a, a, b are each palindromes   OK
cut aa|b    -> [aa, b]       aa and b are palindromes       OK
cut aab     -> [aab]         aab is NOT a palindrome         X

answer: [[a, a, b], [aa, b]]

Clarifying questions

Naming the guarantees before coding shows you reason about inputs, not just the happy path.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Is the string always non-empty and only lowercase letters?”

With length at least 1 there is always at least one partition; a tight alphabet keeps the palindrome check simple.

Output shape

“Does the order of partitions in the answer matter?”

If any order is accepted you can emit partitions as you find them instead of sorting.

“Can a piece be a single character?”

Yes, single letters are palindromes, so the all-singletons partition is always valid.

Constraints & scale

“What is the maximum length of s?”

At length up to 16 the number of partitions can reach 2^(n-1), so an exponential enumeration is expected and fine.

The ideal opening — say it like this

Before I code, a few quick clarifications.

Can I assume s is non-empty and all lowercase letters?

Is any ordering of the partitions acceptable in the output?

And since n is at most 16, an exponential number of partitions is the expected target, right?

Key observations

1Aha

There is always at least one answer

Every single character is a palindrome, so cutting between every letter is always valid. Longer palindromic pieces just give you extra ways to cut.

2Aha

Fix the first piece, then recurse

Choose the first piece as some prefix s[start..end]. If that prefix is a palindrome, keep it and solve the exact same problem on the remaining suffix s[end+1..].

aab
^ start = 0
try a   (palindrome) -> recurse on ab
try aa  (palindrome) -> recurse on b
try aab (no)         -> skip

3Aha

Stop re-checking the same substring

The naive check tests s[i..j] from scratch every time. But s[i..j] is a palindrome exactly when s[i] == s[j] and the inside s[i+1..j-1] already is. Precompute a table pal[i][j] once, and every cut test becomes O(1).

Brute force vs optimal

	Brute force	Optimal
Palindrome check	O(n) per cut	O(1) via DP table
Time	O(n · 2ⁿ)	O(n · 2ⁿ)
Space	O(n)	O(n²)

Both explore the same exponential set of partitions; the optimal one simply refuses to recompute palindrome checks. See the full code in the Approaches selector below.

Summary

Key takeaway

Enumerate choices with backtracking, and when a per-step test repeats on overlapping ranges, precompute it once. Here: try every palindromic prefix, recurse on the rest, and answer "is this a palindrome?" in O(1) from an interval-DP table.

build pal[i][j] for all i <= j      # s[i]==s[j] and pal[i+1][j-1]
backtrack(start, path):
    if start == n: record copy of path; return
    for end in start..n-1:
        if pal[start][end]:
            path.push(s[start..end])
            backtrack(end+1, path)
            path.pop()