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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Palindrome Partitioning and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →