Understanding Palindrome Partitioning in Java

What We're Solving & String Division

Deconstructing sequences into structured, symmetrical subcomponents is a classical problem in text processing and parser design. The Palindrome Partitioning problem asks us to divide a given string s into all possible groups of substrings such that every substring in a group is a palindrome.

A palindrome is a word or character sequence that reads the same backward as forward (for instance, "aba", "a", or "racecar").

For a string like "aab", there are multiple ways to partition it, but only some yield exclusively palindromic components:

• Valid Partitioning: The group [["a", "a", "b"], ["aa", "b"]] is valid because each subset element is symmetric.
• Invalid Partitioning: The group ["a", "ab"] is invalid because the substring "ab" is not a palindrome.

Generating these configurations requires exploring character boundaries recursively. Combining backtracking with two-pointer validation is the optimal approach for this problem.

The Strategy

DFS Backtracking Search Strategy (Time O(N * 2^N), Space O(N))

Let's look at the implementation details of this recursive depth-first search (DFS) strategy:

• Search Boundaries: We try all possible cut sizes starting from index 0.
• Base Case: If our start index reaches the length of string s, we have successfully partitioned the entire string. We create a deep copy of the current path list and add it to our final results list.
• Sub-segment Scan: We iterate an ending boundary index end from start + 1 to s.length().
• Validation Check: For each partition candidate, we extract the substring s.substring(start, end) and check if it is a palindrome using a standard two-pointer check.
• Branch Exploration: If the substring is a palindrome, we add it to our active partition path list, recursively call the backtracking function starting at index end, and then backtrack by removing the substring from our path list before exploring the next ending index.

Detailed Trace Walkthrough

Let's trace this backtracking execution path for the input string s = "aab":

1. Step 1 (Root Call): We execute backtrack(start=0, path=[]).
   • We scan end = 1: Substring is "a". Since "a" is a palindrome, we add it: path = ["a"]. Recurse to index 1.
2. Step 2 (Recurse at Index 1): We execute backtrack(start=1, path=["a"]).
   • We scan end = 2: Substring is "a". Since "a" is a palindrome, we add it: path = ["a", "a"]. Recurse to index 2.
3. Step 3 (Recurse at Index 2): We execute backtrack(start=2, path=["a", "a"]).
   • We scan end = 3: Substring is "b". Since "b" is a palindrome, we add it: path = ["a", "a", "b"]. Recurse to index 3.
4. Step 4 (Base Case): We execute backtrack(start=3, path=["a", "a", "b"]).
   • Since start == s.length(), we save a copy of the path. Results: [["a", "a", "b"]]. We return to the caller.
5. Step 5 (Backtrack at Index 2):
   • We pop the last element "b", returning the path to ["a", "a"]. The loop finishes, and we return.
6. Step 6 (Backtrack at Index 1):
   • We pop the last element "a", returning the path to ["a"].
   • We continue scanning at end = 3: Substring is "ab". Since "ab" is not a palindrome, we skip it. The loop finishes, and we return.
7. Step 7 (Backtrack to Root):
   • We pop the last element "a", returning the path to [].
   • We continue scanning at end = 2: Substring is "aa". Since "aa" is a palindrome, we add it: path = ["aa"]. Recurse to index 2.
   • Inside recursion: We scan end = 3, giving substring "b". Since "b" is a palindrome, we add it: path = ["aa", "b"]. Recurse to index 3.
   • Base Case Reached: Save copy. Final results: [["a", "a", "b"], ["aa", "b"]].

Code Highlights & Explanations

Key highlights of our Java implementation:

• s.substring(start, end) extracts substring slices. The starting index shifts forward to avoid reusing processed characters.
• if (isPalindrome(substr)) checks constraints early, pruning the search branch to avoid wasting CPU cycles.
• path.add(substr); backtrack(end, ...); path.remove(path.size() - 1) implements state choice, forward recursion, and state restoration.

Java Solution

Below is the complete, self-contained Java source code that solves this problem using DFS backtracking, along with a main method to print the partitions.

package io.practise.dsa;
 
import java.util.*;
 
public class PalindromePartitioning {
 
    // Backtracking + isPalindrome: Time O(N * 2^N), Space O(N)
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return res;
        }
        backtrack(0, s, new ArrayList<>(), res);
        return res;
    }
 
    private void backtrack(int start, String s, List<String> path, List<List<String>> res) {
        // Base case: If we reached the end of the string, save the current partition path
        if (start == s.length()) {
            res.add(new ArrayList<>(path)); // Deep copy
            return;
        }
 
        // Try partitioning the string into all possible substring choices
        for (int end = start + 1; end <= s.length(); end++) {
            String substr = s.substring(start, end);
            
            // Only proceed if the current partition is a palindrome
            if (isPalindrome(substr)) {
                // 1. Choose: Add substring to the current partition path
                path.add(substr);
 
                // 2. Explore: Recurse on the remaining part of the string
                backtrack(end, s, path, res);
 
                // 3. Unchoose: Backtrack by removing the substring
                path.remove(path.size() - 1);
            }
        }
    }
 
    private boolean isPalindrome(String s) {
        int l = 0;
        int r = s.length() - 1;
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--)) {
                return false;
            }
        }
        return true;
    }
 
    public static void main(String[] args) {
        PalindromePartitioning solver = new PalindromePartitioning();
        String s = "aab";
 
        System.out.println("--- Palindrome Partitioning Demonstration ---");
        System.out.println("Input String: " + s);
        List<List<String>> partitions = solver.partition(s);
        System.out.println("Palindromic Partitions: " + partitions);
    }
}

Conclusion & Takeaways

Palindrome Partitioning shows how backtracking can explore combinatorial string slices. By skipping non-palindromic branches early, we prune the search tree to retrieve only valid symmetric partitions efficiently.