Palindrome partitioning is a common algorithmic challenge that involves splitting a string into several segments, where each segment reads the same forwards and backwards. This article explores two distinct variations of this problem: finding the minimum number of cuts required and generating all possible valid partitions.

1. Calculating the Minimum Number of Cuts

In this scenario, given a string s, the goal is to determine the fewest number of cuts needed such that every resulting substring is a palindrome. For example, the string "aab" can be split into ["aa", "b"] with just one cut.

An efficient approach uses dynamic programming combined with a center-expansion technique. We maintain an array min_cuts where min_cuts[i] represents the minimum cuts for the prefix of length i. By treating every character (and the gap between characters) as a potential palindrome center, we can update the minimum cuts required for the reached boundaries.

#include <vector>
#include <string>
#include <algorithm>

class PalindromeCutter {
public:
    int getMinCuts(std::string s) {
        int n = s.length();
        if (n <= 1) return 0;

        // dp[i] is the min cuts for the first i characters
        // Initializing with the maximum possible cuts (i-1)
        std::vector<int> dp(n + 1);
        for (int i = 0; i <= n; ++i) {
            dp[i] = i - 1;
        }

        for (int center = 0; center < n; ++center) {
            // Expansion for odd-length palindromes
            expandAroundCenter(s, center, center, dp);
            // Expansion for even-length palindromes
            expandAroundCenter(s, center, center + 1, dp);
        }

        return dp[n];
    }

private:
    void expandAroundCenter(const std::string& s, int left, int right, std::vector<int>& dp) {
        int n = s.length();
        while (left >= 0 && right < n && s[left] == s[right]) {
            // If s[left...right] is a palindrome, 
            // we can update dp[right+1] using dp[left] + 1 cut
            dp[right + 1] = std::min(dp[right + 1], dp[left] + 1);
            left--;
            right++;
        }
    }
};

2. Generating All Possible Palindromic Partitions

Unlike finding a minimum count, this variation requires retrieving every possible sequence of palindromes that reconstructs the original string. If the input is "dde", the valid results are [["d", "d", "e"], ["dd", "e"]].

This is best solved using backtracking (Depth-First Search). We explore every possible prefix of the current string. If the prefix is a palindrome, we record it and recursively process the remaining suffix. To optimize performance, the palindrome check can be performed via a helper function or pre-calculated using a 2D boolean table.

#include <vector>
#include <string>

class PalindromeGenerator {
public:
    std::vector<std::vector<std::string>> partition(std::string s) {
        std::vector<std::vector<std::string>> all_partitions;
        std::vector<std::string> current_list;
        backtrack(s, 0, current_list, all_partitions);
        return all_partitions;
    }

private:
    void backtrack(const std::string& s, int start, std::vector<std::string>& current, 
                   std::vector<std::vector<std::string>>& result) {
        if (start >= s.length()) {
            result.push_back(current);
            return;
        }

        for (int end = start; end < s.length(); ++end) {
            if (isPalindrome(s, start, end)) {
                // Choose: add the current palindromic substring
                current.push_back(s.substr(start, end - start + 1));
                // Explore: move to the next part of the string
                backtrack(s, end + 1, current, result);
                // Unchoose: backtrack for other possibilities
                current.pop_back();
            }
        }
    }

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

The first algorithm focuses on optimization (minimizing an integer value) using Dynamic Programming, while the second focuses on exploration (finding all solutions) using Backtracking. Both leverage the fundamental properties of palindromes but apply different computational strategies to meet their respective objectives.