Palindrome Partitioning

Mediumbacktrackingstringdynamic-programming
Category: Backtracking
Companies that ask this question:
AmazonGoogleFacebookMicrosoft
LeetCode →NeetCode →

Approach

Palindrome Partitioning

Problem Statement

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

Examples

Example 1

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

Example 2

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

Intuition

Goal: Split string into parts where each part is a palindrome.

For "aab":

  • Can split as ["a", "a", "b"] (all single chars are palindromes)
  • Or ["aa", "b"] (aa is palindrome)

Approach: Try all possible splits, keep those where all parts are palindromes.

Pattern Recognition

This is a Backtracking with Validation problem:

  • Explore all partitions
  • Validate each substring (is palindrome?)
  • Collect valid partitions

Approach

def backtrack(start, current):
  if start == len(s):
    result.append(current.copy())
    return

  for end in range(start + 1, len(s) + 1):
    substring = s[start:end]
    if is_palindrome(substring):
      current.append(substring)
      backtrack(end, current)
      current.pop()

Optimization: Cache palindrome checks with DP.

Complexity Analysis

  • Time: O(n × 2^n)

    • 2^n possible partitions
    • O(n) to check palindrome

  • Space: O(n) recursion depth

Solution

java
1import java.util.*;
2
3class Solution {
4    public List<List<String>> partition(String s) {
5        List<List<String>> result = new ArrayList<>();
6        backtrack(s, 0, new ArrayList<>(), result);
7        return result;
8    }
9
10    private void backtrack(String s, int start, List<String> current, List<List<String>> result) {
11        if (start == s.length()) {
12            result.add(new ArrayList<>(current));
13            return;
14        }
15
16        for (int end = start + 1; end <= s.length(); end++) {
17            String substring = s.substring(start, end);
18            if (isPalindrome(substring)) {
19                current.add(substring);
20                backtrack(s, end, current, result);
21                current.remove(current.size() - 1);
22            }
23        }
24    }
25
26    private boolean isPalindrome(String s) {
27        int left = 0, right = s.length() - 1;
28        while (left < right) {
29            if (s.charAt(left++) != s.charAt(right--)) {
30                return false;
31            }
32        }
33        return true;
34    }
35}
36
Loading visualizer...