Palindrome Partitioning

Medium Problem 93 of 151 Java and Python

Problem

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

Example 1

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

Example 2

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

Constraints

1 ≤ s.length ≤ 16
s contains only lowercase English letters.

Explanation

Choose the first piece: any palindromic prefix s[0..end]. Then partition the rest of the string the same way. Each complete path of choices is one partition.

Checking "is s[i..j] a palindrome?" repeatedly is wasteful; a DP table answers it in O(1) after O(n²) setup.

Approach 1 · Better

Backtracking with direct palindrome checks

Time O(n · 2ⁿ)
Space O(n) recursion

At position start, try every end index; if s[start..end] is a palindrome (checked with two pointers), take it and recurse from end + 1.

backtrack(start): if start == n, record the path.
For each end ≥ start: if s[start..end] is a palindrome, push it, recurse with end + 1, pop.

Java

import java.util.*;

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(String s, int start, List<String> path, List<List<String>> result) {
        if (start == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int end = start; end < s.length(); end++) {
            if (isPalindrome(s, start, end)) {
                path.add(s.substring(start, end + 1));
                backtrack(s, end + 1, path, result);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int i, int j) {
        while (i < j) {
            if (s.charAt(i++) != s.charAt(j--)) {
                return false;
            }
        }
        return true;
    }
}

Python

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result, path = [], []

        def backtrack(start):
            if start == len(s):
                result.append(path[:])
                return
            for end in range(start, len(s)):
                piece = s[start:end + 1]
                if piece == piece[::-1]:
                    path.append(piece)
                    backtrack(end + 1)
                    path.pop()

        backtrack(0)
        return result

Approach 2 · Optimal

Backtracking with a palindrome table

Time O(n · 2ⁿ), with O(n²) setup
Space O(n²)

Precompute pal[i][j] (is s[i..j] a palindrome?) with dynamic programming, then backtrack using O(1) lookups.

pal[i][j] = s[i] == s[j] && (j - i < 2 || pal[i + 1][j - 1]), filling i from the end.
Backtrack exactly as before, but test pal[start][end].

Java

import java.util.*;

class Solution {
    public List<List<String>> partition(String s) {
        int n = s.length();
        boolean[][] pal = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]);
            }
        }
        List<List<String>> result = new ArrayList<>();
        backtrack(s, pal, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(String s, boolean[][] pal, int start, List<String> path, List<List<String>> result) {
        if (start == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int end = start; end < s.length(); end++) {
            if (pal[start][end]) {
                path.add(s.substring(start, end + 1));
                backtrack(s, pal, end + 1, path, result);
                path.remove(path.size() - 1);
            }
        }
    }
}

Python

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        pal = [[False] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])
        result, path = [], []

        def backtrack(start):
            if start == n:
                result.append(path[:])
                return
            for end in range(start, n):
                if pal[start][end]:
                    path.append(s[start:end + 1])
                    backtrack(end + 1)
                    path.pop()

        backtrack(0)
        return result

Complexity compared

Approach	Time	Space
Better Backtracking with direct palindrome checks	O(n · 2ⁿ)	O(n) recursion
Optimal Backtracking with a palindrome table	O(n · 2ⁿ), with O(n²) setup	O(n²)

Key takeaways

Backtracking + DP is common: precompute the expensive check, then enumerate.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem