Find all possible palindromic partitions of a String

Given a String S, Find all possible Palindromic partitions of the given String.

• Time : O(2^n)
• Space : O(n)

c++

class Solution {
    vector<int> dp;
    void manacher(string _s) {
        string s = "#";
        for(auto& ch : _s) {
            s.push_back(ch);
            s.push_back('#');
        }
        
        int l = 0, r = -1, n = s.length();
        dp = vector<int>(n);
        
        for(int i = 0; i < n; i++) {
            dp[i] = max(0, min(r - i, (r + l - i >= 0 ? dp[r + l - i] : -1)));
            while(i + dp[i] < n and i - dp[i] >= 0 and s[i + dp[i]] == s[i - dp[i]]) dp[i]++;
            if(i + dp[i] > r) {
                r = i + dp[i];
                l = i - dp[i];
            }
        }
    }
    
    bool palindrome(int l, int r) {
        int left = l * 2 + 1, right = r * 2 + 1;
        int mid = left + (right - left) / 2;
        return mid + dp[mid] > right;
    }
    
    void helper(vector<vector<string>>& res, vector<string>& builder, string& s, int pos) {
        if(pos == s.length()) res.push_back(builder);
        else {
            for(int i = pos; i < s.length(); i++) {
                if(palindrome(pos, i)) {
                    builder.push_back(s.substr(pos,i - pos + 1));
                    helper(res, builder, s, i + 1);
                    builder.pop_back();
                }
            }
        }
    }
public:
    vector<vector<string>> allPalindromicPerms(string S) {
        vector<vector<string>> res;
        manacher(S);
        helper(res, vector<string>() = {}, S, 0);
        return res;
    }
};