Palindrome Partitioning

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

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.

Approach: Backtracking with Palindrome Check

Algorithm

1. Use a recursive function that builds partitions starting from index start
2. For each possible end index, check whether s[start..end] is a palindrome
3. If it is, add it to the current partition and recurse from end + 1
4. When start reaches the end of the string, record the complete partition
5. Backtrack by removing the last added substring

Time & Space Complexity

• Time Complexity: O(n · 2^n) - in the worst case (all same characters) there are 2^n partitions
• Space Complexity: O(n) - recursion depth (excluding the output)

Java Implementation

import java.util.ArrayList;
import java.util.List;

public class PalindromePartitioning {

    /**
     * Return all possible palindrome partitionings of s.
     * @param s Input string
     * @return List of partitions where every substring is a palindrome
     */
    public static List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), result);
        return result;
    }

    private static 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);
            }
        }
    }

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

    // Test method
    public static void main(String[] args) {
        System.out.println("Input: s = \"aab\"");
        System.out.println("Output: " + partition("aab"));
        // Expected: [[a, a, b], [aa, b]]

        System.out.println("Input: s = \"a\"");
        System.out.println("Output: " + partition("a"));
        // Expected: [[a]]
    }
}

Example Walkthrough

For s = "aab":

1. start=0: “a” is a palindrome. Recurse at start=1.
2. start=1: “a” is a palindrome. Recurse at start=2.
3. start=2: “b” is a palindrome. Recurse at start=3 (complete). Partition: [“a”, “a”, “b”]
4. Back to start=1: “ab” is not a palindrome.
5. Back to start=0: “aa” is a palindrome. Recurse at start=2.
6. start=2: “b” is a palindrome. Partition: [“aa”, “b”]

Answer: [["a","a","b"],["aa","b"]].

Key Points

1. Palindrome Check: A substring is valid only if it reads the same forwards and backwards
2. Substring Choice: Each recursion level chooses the next palindrome starting at start
3. Copy on Complete: Add new ArrayList<>(current) to store an independent partition
4. Worst-Case Explosion: Strings of repeated characters produce the maximum number of partitions
5. Small Constraint: s.length <= 16 keeps the output manageable