Skip to main content

131. Palindrome Partitioning

medium

Partition a string into substrings such that every substring is a palindrome, and return every possible partitioning. Stacks an is-palindrome check inside a classic substring backtracking template.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Constraints

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

Examples

Example 1

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

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Recurse with a start index and a current path of substrings.

Hint 2

At each call, loop end from start to length - 1. If s.substring(start, end + 1) is a palindrome, push it, recurse(end + 1), pop.

Hint 3

Base case: start == length -> snapshot.

Hint 4

Precomputing an isPalin[i][j] DP table flips the per-check cost from O(n) to O(1).

Solution approach

Reveal approach

Backtrack with (start, path). When start == s.length, snapshot path. Otherwise loop end from start to s.length - 1: if s.substring(start, end + 1) is a palindrome, push it onto path, recurse with start = end + 1, pop. Palindrome check is two pointers from each end — O(end - start). For a tighter bound, precompute a 2D isPalin[i][j] table: isPalin[i][j] = (s[i] == s[j]) && (j - i < 2 || isPalin[i+1][j-1]). Build in O(n^2) time, query in O(1). Time complexity: O(n * 2^n) — there are up to 2^n partition points and producing the result of length up to n at each leaf. Space: O(n) recursion plus optional O(n^2) for the palindrome table.

Complexity

Time
O(n * 2^n)
Space
O(n)

Related patterns

  • backtracking
  • recursion
  • palindrome

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Bloomberg
  • Uber

More Recursion practice problems

See all Recursion problems →