1.5) Palindrome Partitioning of String

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 is a string that reads the same backward as forward.

Sample Input/Output:

Let’s consider a sample input:

s = "aab"

Expected Output:

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

Explanation:
For the given input “aab”, there are two possible palindrome partitioning:

1. [“a”, “a”, “b”]: All substrings (“a”, “a”, and “b”) are palindromes.
2. [“aa”, “b”]: All substrings (“aa” and “b”) are palindromes.

Time and Space Complexity:

The time complexity of the solution will be O(N * 2^N), where N is the length of the string s. For each character in the string, there are 2 choices: either include it as a single-character palindrome or include it as part of a longer palindrome. The number of possible partitions is 2^N.

The space complexity will be O(N) to store the current partition and O(N * 2^N) to store all possible partitions.

Now, let’s implement the solution in C++:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

bool isPalindrome(const string& s, int start, int end) {
    while (start < end) {
        if (s[start++] != s[end--]) {
            return false;
        }
    }
    return true;
}

vector<vector<string>> partition(string s) {
    vector<vector<string>> result;
    vector<string> currentPartition;

    // Helper function to backtrack and generate palindrome partitions
    void backtrack(int start) {
        if (start == s.length()) {
            result.push_back(currentPartition);
            return;
        }

        for (int end = start; end < s.length(); ++end) {
            if (isPalindrome(s, start, end)) {
                currentPartition.push_back(s.substr(start, end - start + 1));
                backtrack(end + 1);
                currentPartition.pop_back();
            }
        }
    }

    backtrack(0);

    return result;
}

int main() {
    string s = "aab";
    vector<vector<string>> result = partition(s);

    cout << "Palindrome Partitions:\n";
    for (const auto& partition : result) {
        cout << "[";
        for (const string& palindrome : partition) {
            cout << "\"" << palindrome << "\" ";
        }
        cout << "]" << endl;
    }

    return 0;
}

In this implementation, we use backtracking to generate all possible palindrome partitions. The isPalindrome function is a helper function to check if a substring of the input string s is a palindrome.

The backtrack function is a recursive function that explores all possible choices for each substring in the input s. It uses the isPalindrome function to check if the current substring is a palindrome. If it is, the substring is added to the current partition, and the function is called recursively to explore the next substring.

The main function demonstrates the usage of partition by finding all possible palindrome partitions for the given input s.

The output will be:

Palindrome Partitions:
["a" "a" "b" ]
["aa" "b" ]