Palindrome Partitioning

public class Solution {
    public String[][] partition(String s) {
        // Your code goes here
    }
}

Building Intuition

Given a word like "noon", we want to find every possible way to split it into segments where each segment is a palindrome.

Every single character is automatically a palindrome. So one valid partition is always splitting into individual characters. But we can also group consecutive characters together if they form a palindrome.

Finding All Partitions

The problem asks us to find all possible partitions, not just one. We can't just greedily take the longest palindrome at each step; we need to explore every valid way to split the string.

Think of partitioning as making cuts. At each position start, you're choosing where to end your next segment. You pick an end index and commit to the segment s[start..end]. The only rule? That segment must be a palindrome.

For the string "noon":

• Cut after index 0 → segment "n" (palindrome ✓) → recurse on "oon"
• Cut after index 1 → segment "no" (not palindrome ✗) → skip
• Cut after index 2 → segment "noo" (not palindrome ✗) → skip
• Cut after index 3 → segment "noon" (palindrome ✓) → recurse on ""

Once you frame it this way, the recursion becomes simple: from position start, try every possible end. If s[start..end] is a palindrome, add it to your current path and recurse from end + 1. When start == n, you've reached the end, so record the path.

This is backtracking: make a choice (commit to a palindrome segment), explore what follows, then undo that choice and try a different cut.

The Solution-Space Tree

Each partitioning problem can be visualized as a tree. Each node represents a recursive call with a particular start position. From each node, we branch out to try different ending positions. Each branch represents "take s[start..end] as the next segment."

Here's the complete solution-space tree for "noon":

The tree shows a glimpse of how backtracking works, notice how "no", "noo", "oon", and "on" all get pruned because they're not palindromes. We end up with 3 valid partitions: ["n","o","o","n"], ["n","oo","n"], and ["noon"]. Let's understand this below thoroughly.

The Algorithm

The algorithm follows directly from the tree structure. Each node represents a recursive call at position start. For each call, we try all possible cuts:

Checking for Palindromes

A string is a palindrome if it reads the same forwards and backwards. We can check this by comparing characters from both ends moving inward:

isPalindrome(s, left, right)
    while left < right
        if s[left] != s[right]
            return false
        left = left + 1
        right = right - 1
    return true

Here's the complete algorithm:

partition(s)
    result = []
    path = []
    backtrack(s, 0, path, result)
    return result

backtrack(s, start, path, result)
    if start == length(s)           // reached the end, valid partition!
        result.add(copy of path)
        return
    
    for end from start to length(s) - 1     // try all cut positions
        if isPalindrome(s, start, end)      // only proceed if segment is palindrome
            path.add(s[start..end])         // commit to this cut
            backtrack(s, end + 1, path, result)  // recurse from end+1
            path.removeLast()               // undo the cut (backtrack)

The loop for end from start to length(s) - 1 tries every possible cut position. If s[start..end] is a palindrome, we commit to that segment (add it to path), then recurse to partition the remainder starting at end + 1. When we return, we undo the choice and try the next cut position.

Step-by-Step Walkthrough

Let's trace through s = "noon" step by step, watching how we traverse the solution-space tree. This is essentially a depth-first traversal of the tree we discussed above.

Here's the complete tree for reference (same as above, showing all branches):

Now let's walk through the DFS traversal:

Step 1: Start with "n"

Starting at root, we try the first cut: take "n". It's a single character (always a palindrome), so we recurse.

Step 2: Continue with "o", then another "o"

Following the DFS, we take "o" (palindrome), then another "o" (palindrome).

Step 3: Take "n" — found first partition!

Taking "n" completes the path. Now start = 4, which equals length("noon"). We've found our first complete partition!

Step 4: Backtrack, try "oo" — found second partition!

We backtrack and try "oo" instead of "o". It's a palindrome (reads same forwards and backwards)! Then we take "n" and find another complete partition.

Step 5: Backtrack to root, try "noon" — found third partition!

We backtrack all the way to the root and try "noon". The entire string is a palindrome! This gives us our third complete partition.

Final Result

The complete traversal found 3 valid partitions:

Solution

The backtracking algorithm systematically explores all possible ways to partition the string. At each position, we try every possible palindromic prefix and recursively solve for the remainder.

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

Optimization: Precompute Palindromes

We can avoid redundant palindrome checks by precomputing a 2D table where dp[i][j] tells us whether s[i..j] is a palindrome. This uses dynamic programming:

• Single characters: dp[i][i] = true
• Two characters: dp[i][i+1] = (s[i] == s[i+1])
• Longer: dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]

This changes each palindrome check from O(n) to O(1), but the overall complexity remains because we still need to enumerate all partitions.