<p>Given a string <code>s</code>, partition <code>s</code> such that every <span data-keyword="substring-nonempty">substring</span> of the partition is a <span data-keyword="palindrome-string"><strong>palindrome</strong></span>. Return <em>all possible palindrome partitioning of </em><code>s</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> s = "aab"
<strong>Output:</strong> [["a","a","b"],["aa","b"]]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = "a"
<strong>Output:</strong> [["a"]]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 16</code></li>
	<li><code>s</code> contains only lowercase English letters.</li>
</ul>

#include <stack>
#include <string_view>
#include <ranges>

struct View {
    std::size_t begin;
    std::size_t end;
};

using Palindromes = std::vector<View>;

vector<Palindromes> scan(const string& str) {
    vector<Palindromes> res;
    res.emplace_back().emplace_back(View{0, 1});
    for(std::size_t k=1; k<str.size(); ++k) {
        char c = str[k];
        Palindromes to_add;
        to_add.emplace_back(View{k, k+1});
        if(str[k-1] == str[k]) {
            to_add.emplace_back(View{k-1, k+1});
        }
        for(const auto& prev : res.back()) {
            if(prev.begin != 0 && str[prev.begin - 1] == str[k]) {
                to_add.emplace_back(View{prev.begin-1, k+1});
            }
        }
        res.emplace_back(std::move(to_add));
    }
    return res;
}

class Solution {
public:


vector<vector<string>> partition(string s) {
    auto cache = scan(s);
    struct Element {
        vector<View> cumulated;

        vector<string> convert(const string& s) const {
            auto rng = std::ranges::subrange{cumulated.rbegin(), cumulated.rend()} 
                     | std::views::transform([&s](const View& v){
                        return string{s, v.begin, v.end - v.begin};
                     });
            return vector<string>{rng.begin(), rng.end()};
        }
    };

    
    vector<vector<string>> res;
    stack<Element> open;
    for(const auto& last : cache.back()) {
        open.emplace().cumulated.push_back(last);
    }
    while (!open.empty()) {
        auto top = open.top();
        open.pop();
        if(top.cumulated.back().begin == 0) {
            res.emplace_back(top.convert(s));
        }
        else {
            for(const auto& next : cache[top.cumulated.back().begin-1]) {
                auto to_add = top;
                to_add.cumulated.push_back(next);
                open.emplace(std::move(to_add));
            }
        }
    }
    return res;
}

};
187115