Palindrome Partitioning Using Backtracking in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Palindrome Partitioning for "aab"

What is the output of the following Java code that finds all palindrome partitions of the string "aab"?

DSA Java

import java.util.*;

public class PalindromePartitioning {
    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 left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) return false;
        }
        return true;
    }

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

A [["a", "ab"]]

B [["a", "a", "b"], ["aa", "b"]]

C [["aab"]]

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

💡 Hint

Think about all ways to split the string into substrings that read the same forwards and backwards.

The code finds all partitions where each substring is a palindrome. For "aab", the valid partitions are ["a", "a", "b"] and ["aa", "b"].

🧠 Conceptual

intermediate

Understanding Backtracking in Palindrome Partitioning

In the palindrome partitioning backtracking approach, what is the main reason for removing the last added substring after the recursive call?

A To optimize the palindrome checking process

B To permanently remove invalid substrings from the result

C To explore other possible partitions by undoing the last choice

D To sort the substrings in lexicographical order

💡 Hint

Backtracking means trying and then undoing choices to try others.

Removing the last added substring allows the algorithm to backtrack and try different partitions starting from the previous state.

🔧 Debug

advanced

Identify the Error in Palindrome Partitioning Code

What error will occur if the isPalindrome method is incorrectly implemented as below? private static boolean isPalindrome(String s, int left, int right) { while (left <= right) { if (s.charAt(left) != s.charAt(right)) return false; left++; right--; } return true; }

A Incorrect palindrome detection due to wrong loop condition

B IndexOutOfBoundsException when left or right goes beyond string length

C Infinite loop because left and right are not updated

D No error; the method works correctly

💡 Hint

Check if the loop condition and pointer updates are correct for palindrome checking.

The loop condition 'left <= right' and pointer increments ensure all characters are checked correctly. This method works fine.

❓ Predict Output

advanced

Output of Palindrome Partitioning for "racecar"

What is the output of the palindrome partitioning code for the input string "racecar"?

DSA Java

import java.util.*;

public class PalindromePartitioning {
    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 left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) return false;
        }
        return true;
    }

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

A [["r", "a", "c", "e", "c", "a", "r"], ["r", "a", "cec", "a", "r"], ["r", "aceca", "r"], ["racecar"]]

B [["r", "aceca", "r"], ["racecar"]]

C [["r", "a", "c", "e", "c", "a", "r"]]

D [["racecar"]]

💡 Hint

Look for all palindrome substrings and their combinations.

The code finds all palindrome partitions including single letters and larger palindromes like "cec", "aceca", and the whole "racecar".

🚀 Application

expert

Minimum Cuts for Palindrome Partitioning

Given the string "ababbbabbababa", what is the minimum number of cuts needed to partition it into palindromic substrings?

A 4

B 3

C 5

D 6

💡 Hint

Try to find the fewest cuts so that every substring is a palindrome.

The minimum cuts needed for "ababbbabbababa" is 4, partitioning into palindromes like ["a", "babbbab", "b", "ababa"] or similar.

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