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"]]

Example 2:

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

Steps

1. Backtracking: We will use a backtracking algorithm to explore all possible partitions.
2. Palindrome Check: For each substring, we need a helper function to efficiently check if it's a palindrome.
3. Partition Storage: We'll use a list to store the current partition being built.
4. Result Storage: A list of lists will store all valid palindrome partitions.
5. Base Case: When the entire input string has been processed, add the current partition to the result.
6. Recursive Step: Iterate through possible splitting points. For each split, check if the substring is a palindrome. If it is, add it to the current partition, recursively call the function with the remaining substring, and then backtrack (remove the added substring).

Explanation

The solution uses backtracking to explore all possible ways to partition the input string. The isPalindrome function efficiently checks if a substring is a palindrome. The main function partition recursively explores all possible partitions. At each step, it considers splitting the string at different points. If the substring before the split is a palindrome, it adds it to the current partition and recursively calls itself with the remaining substring. After the recursive call returns, it backtracks by removing the last added palindrome from the current partition to explore other possibilities. This ensures that all possible palindrome partitions are explored.

Code

function isPalindrome(s: string): boolean {
    let left = 0;
    let right = s.length - 1;
    while (left < right) {
        if (s[left] !== s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

function partition(s: string): string[][] {
    const result: string[][] = [];
    const currentPartition: string[] = [];

    function backtrack(index: number) {
        if (index === s.length) {
            result.push([...currentPartition]); // Add a copy to avoid modification
            return;
        }

        for (let i = index; i < s.length; i++) {
            const substring = s.substring(index, i + 1);
            if (isPalindrome(substring)) {
                currentPartition.push(substring);
                backtrack(i + 1);
                currentPartition.pop(); // Backtrack
            }
        }
    }

    backtrack(0);
    return result;
}


// Example usage
console.log(partition("aab")); // Output: [["a","a","b"],["aa","b"]]
console.log(partition("a"));  // Output: [["a"]]
console.log(partition("bb")); // Output: [["b","b"],["bb"]]

Complexity

• Time Complexity: O(N * 2^N), where N is the length of the string. In the worst case, we might need to explore all possible partitions, which is exponential. The palindrome check is O(N/2) which simplifies to O(N).
• Space Complexity: O(N * 2^N) in the worst case to store all possible partitions in the result. The recursive call stack could also take up to O(N) space.