Palindrome Partitioning medium

Problem Statement

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

A palindrome string is a string that reads the same backward as forward.

Example 1:

Input: s = "aab" Output: [["a","a","b"],["aa","b"]] Explanation: The possible palindrome partitions are ["a","a","b"] and ["aa","b"].

Example 2:

Input: s = "a" Output: [["a"]]

Steps and Explanation

This problem can be solved using backtracking. The core idea is to explore all possible partitions of the string. For each partition, we check if the current substring is a palindrome. If it is, we add it to the current partition and recursively explore the remaining string. If it's not a palindrome, we backtrack and try a different partition.

Here's a breakdown of the steps:

1. Base Case: If the string is empty, we've found a valid partition. Add the current partition to the result list.

2. Recursive Step: Iterate through the string. For each character, consider it as the ending point of a substring.

3. Palindrome Check: Check if the substring from the beginning of the string to the current character is a palindrome. We can do this using a helper function.

4. Recursive Call: If the substring is a palindrome, add it to the current partition, and recursively call the function with the remaining substring.

5. Backtracking: After the recursive call returns, remove the last added palindrome from the current partition to explore other possibilities.

Code (Java)

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

public class PalindromePartitioning {

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

    private void backtrack(String s, int start, List<String> currentPartition, List<List<String>> result) {
        if (start == s.length()) {
            result.add(new ArrayList<>(currentPartition)); // Add a copy to avoid modification
            return;
        }

        for (int i = start; i < s.length(); i++) {
            String substring = s.substring(start, i + 1);
            if (isPalindrome(substring)) {
                currentPartition.add(substring);
                backtrack(s, i + 1, currentPartition, result);
                currentPartition.remove(currentPartition.size() - 1); // Backtrack
            }
        }
    }

    private boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        PalindromePartitioning solution = new PalindromePartitioning();
        String s1 = "aab";
        String s2 = "a";
        System.out.println(solution.partition(s1)); // Output: [["a", "a", "b"], ["aa", "b"]]
        System.out.println(solution.partition(s2)); // Output: [["a"]]

    }
}

Complexity Analysis

• Time Complexity: O(N * 2^N), where N is the length of the string. This is because there can be up to 2^N possible partitions, and checking if a substring is a palindrome takes O(N) in the worst case.

• Space Complexity: O(N), primarily due to the recursion depth and the space used by the currentPartition list. The result list can also consume significant space in the worst case.