Palindrome Partitioning Using Backtracking in DSA Java

Mental Model

We try to split a string into parts where each part reads the same forwards and backwards, by exploring all possible splits step-by-step.

Analogy: Imagine cutting a ribbon into pieces so that each piece is a perfect mirror image of itself, and you try every way to cut it until you find all such sets of pieces.

s = "a b a b c"
Indices: 0 1 2 3 4
Partitions: [a] [b] [a] [b] [c]
Each bracket is a substring to check if palindrome

Dry Run Walkthrough

Input: string: "aab"

Goal: Find all ways to split "aab" into substrings where each substring is a palindrome

Step 1: Start from index 0, check substring "a" (0 to 0) if palindrome

["a"] + remaining "ab"

Why: We try the smallest substring first to see if it can be a palindrome part

Step 2: Since "a" is palindrome, recurse from index 1 with current partition ["a"]

["a"] -> check substrings starting at index 1: "a", "ab"

Why: We continue partitioning the rest of the string

Step 3: Check substring "a" (1 to 1), it is palindrome, add to partition

["a", "a"] + remaining "b"

Why: We found another palindrome substring

Step 4: Recurse from index 2 with partition ["a", "a"]

["a", "a"] -> check substring "b" (2 to 2)

Why: Continue partitioning the remaining string

Step 5: Check substring "b" (2 to 2), palindrome, add to partition

["a", "a", "b"] + remaining empty

Why: Reached end with all palindrome parts

Step 6: Add partition ["a", "a", "b"] to results

results = [["a", "a", "b"]]

Why: Found one valid palindrome partition

Step 7: Backtrack to index 1, check substring "ab" (1 to 2), not palindrome, skip

["a"] + remaining "ab" (no addition)

Why: Skip invalid palindrome substring

Step 8: Backtrack to index 0, check substring "aa" (0 to 1), palindrome, add to partition

["aa"] + remaining "b"

Why: Try longer palindrome substring from start

Step 9: Recurse from index 2 with partition ["aa"]

["aa"] -> check substring "b" (2 to 2)

Why: Partition remaining string

Step 10: Check substring "b" (2 to 2), palindrome, add to partition

["aa", "b"] + remaining empty

Why: Reached end with palindrome parts

Step 11: Add partition ["aa", "b"] to results

results = [["a", "a", "b"], ["aa", "b"]]

Why: Found second valid palindrome partition

Result:

results = [["a", "a", "b"], ["aa", "b"]]

Annotated Code

DSA Java

import java.util.*;

public class PalindromePartitioning {

    // Check if substring s[left..right] is palindrome
    private static boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false; // mismatch means not palindrome
            }
            left++;
            right--;
        }
        return true; // all matched
    }

    // Backtracking function to find palindrome partitions
    private static void backtrack(String s, int start, List<String> current, List<List<String>> result) {
        if (start == s.length()) {
            result.add(new ArrayList<>(current)); // reached end, add current partition
            return;
        }

        for (int end = start; end < s.length(); end++) {
            if (isPalindrome(s, start, end)) {
                current.add(s.substring(start, end + 1)); // add palindrome substring
                backtrack(s, end + 1, current, result); // recurse for remaining string
                current.remove(current.size() - 1); // backtrack to try other partitions
            }
        }
    }

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

    public static void main(String[] args) {
        String input = "aab";
        List<List<String>> partitions = partition(input);
        for (List<String> part : partitions) {
            System.out.println(part);
        }
    }
}

if (s.charAt(left) != s.charAt(right)) { return false; }

Check characters from both ends to confirm palindrome

if (start == s.length()) { result.add(new ArrayList<>(current)); return; }

If reached end of string, add current partition to results

for (int end = start; end < s.length(); end++) {

Try all substrings starting at 'start' index

if (isPalindrome(s, start, end)) {

Check if current substring is palindrome before proceeding

current.add(s.substring(start, end + 1));

Add palindrome substring to current partition

backtrack(s, end + 1, current, result);

Recurse to partition remaining substring

current.remove(current.size() - 1);

Backtrack to explore other partitions

Output

[a, a, b]

[aa, b]

Complexity Analysis

Time: O(N * 2^N) because each character can be either cut or not, generating exponential partitions, and palindrome checks take O(N) each

Space: O(N) for recursion stack and current partition storage, plus O(2^N) for storing all partitions

vs Alternative: Compared to naive checking all substrings without pruning, backtracking with palindrome checks avoids invalid partitions early, improving efficiency

Edge Cases

Empty string ""

Returns list with empty partition [[]]

DSA Java

if (start == s.length()) { result.add(new ArrayList<>(current)); return; }

String with all same characters "aaa"

Finds all partitions where substrings are palindromes, including single chars and longer substrings

DSA Java

if (isPalindrome(s, start, end)) {

String with no palindrome longer than 1 "abc"

Partitions only single characters as palindromes

DSA Java

if (isPalindrome(s, start, end)) {

When to Use This Pattern

When asked to find all ways to split a string into palindrome substrings, use backtracking to explore partitions and prune invalid paths early.

Common Mistakes

Mistake: Not backtracking (removing last substring) after recursive call, causing incorrect partitions
Fix: Always remove last added substring after recursion to explore other partitions

Mistake: Checking palindrome inefficiently inside loop causing repeated work
Fix: Use a helper function to check palindrome efficiently or cache results

Summary

It finds all ways to split a string into palindrome substrings using backtracking.

Use it when you need to list all palindrome partitions of a string.

The key insight is to try every substring and backtrack when it is not a palindrome.

Practice

1. What is the main goal of palindrome partitioning using backtracking?

easy

A. To count the number of palindromes in a string

B. To find the longest palindrome substring in a string

C. To split a string into all possible palindrome substrings

D. To reverse the string and check if it is a palindrome

Solution

1. Step 1: Understand palindrome partitioning

   Palindrome partitioning means dividing a string into parts where each part is a palindrome.

2. Step 2: Role of backtracking

   Backtracking helps explore all possible ways to split the string into palindrome parts.

3. Final Answer:

   To split a string into all possible palindrome substrings -> Option C

4. Quick Check:

   Palindrome partitioning = splitting into palindrome substrings [OK]

Hint: Backtracking explores all palindrome splits [OK]

Common Mistakes:

• Confusing palindrome partitioning with longest palindrome substring
• Thinking it only counts palindromes instead of listing partitions
• Assuming it reverses the whole string

2. Which of the following is the correct Java method signature for a backtracking function that partitions a string into palindromes?

easy

A. boolean backtrack(String s, int start, List<String> current)

B. void backtrack(String s, int start, List result, List<String> current)

C. int backtrack(String s, int start, List<String> result)

D. String backtrack(String s, int start, List result)

Solution

1. Step 1: Analyze method parameters

   The method needs the string, current start index, a list to store all partitions, and the current partition path.

2. Step 2: Check return type

   Backtracking methods usually return void because they build results via parameters.

3. Final Answer:

   void backtrack(String s, int start, List result, List<String> current) -> Option B

4. Quick Check:

   Backtracking method returns void and uses lists [OK]

Hint: Backtracking returns void and uses lists for results [OK]

Common Mistakes:

• Using wrong return type like int or boolean
• Missing current partition list parameter
• Returning String instead of void

3. What will be the output partitions for the input string "aab" using palindrome partitioning?

medium

A. [["aab"]]

B. [["aa", "ab"]]

C. [["a", "ab"]]

D. [["a", "a", "b"], ["aa", "b"]]

Solution

1. Step 1: Identify palindrome substrings

   "a" and "aa" are palindromes; "b" is a palindrome; "ab" is not.

2. Step 2: List all palindrome partitions

   Partitions are ["a", "a", "b"] and ["aa", "b"].

3. Final Answer:

   [["a", "a", "b"], ["aa", "b"]] -> Option D

4. Quick Check:

   Only palindrome splits included [OK]

Hint: Check each substring palindrome before partitioning [OK]

Common Mistakes:

• Including non-palindrome substrings like "ab"
• Missing the partition with "aa"
• Returning only one partition

4. Identify the error in this Java backtracking snippet for palindrome partitioning:

void backtrack(String s, int start, List result, List<String> current) {
  if (start == s.length()) {
    result.add(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, result, current);
      current.remove(current.size());
    }
  }
}

medium

A. Incorrect removal index in current.remove()

B. Missing base case for empty string

C. Wrong substring indices in s.substring()

D. Backtracking call uses wrong start index

Solution

1. Step 1: Check removal from current list

   List indices start at 0, so removing at current.size() causes IndexOutOfBoundsException.

2. Step 2: Correct removal index

   Should remove last element with current.remove(current.size() - 1).

3. Final Answer:

   Incorrect removal index in current.remove() -> Option A

4. Quick Check:

   Remove last element with size()-1 [OK]

Hint: Remove last added element with size()-1 index [OK]

Common Mistakes:

• Removing element at size() instead of size()-1
• Confusing substring indices
• Incorrect recursive call start index

5. Given the string "racecar", how many palindrome partitions will the backtracking algorithm generate?

hard

A. 6

B. 8

C. 4

D. 10

Solution

1. Step 1: Identify palindrome substrings in "racecar"

   Palindromes include "r", "a", "c", "e", "cec", "aceca", "racecar" and their combinations.

2. Step 2: Count all palindrome partitions

   Partitions are:
   ["racecar"],
   ["r", "aceca", "r"],
   ["r", "a", "cec", "a", "r"],
   ["r", "a", "c", "e", "c", "a", "r"],
   and others including splits like ["r", "a", "c", "ec", "a", "r"] are invalid because "ec" is not palindrome.
   Counting all valid partitions, the total is 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Count all palindrome partitions = 6 [OK]

Hint: Count all palindrome splits including nested palindromes [OK]

Common Mistakes:

• Counting only single-character partitions
• Missing longer palindrome substrings
• Double counting partitions