#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <algorithm>
using namespace std;

class Solution {
public:
    // Main function: returns the maximum unique split as a vector of strings.
    vector<string> maxUniqueSplit(string s) {
        unordered_set<string> seen;
        auto res = backtrack(s, 0, seen);
        return res.second;
    }

private:
    // Returns a pair {maxCount, splitVector} for substring s[start:].
    // maxCount = maximum number of unique substrings obtainable
    // splitVector = corresponding splitting (in order) that achieves that count.
    pair<int, vector<string>> backtrack(const string &s, int start, unordered_set<string> &seen) {
        int n = s.size();
        if (start == n) {
            // Reached the end: return count 0 and an empty splitting.
            return {0, vector<string>()};
        }

        int maxCount = 0;
        vector<string> bestSplitting;  // best splitting for this subproblem

        // Try every possible substring starting from index 'start'
        for (int end = start + 1; end <= n; ++end) {
            string substring = s.substr(start, end - start);
            // If this substring hasn't been used yet
            if (seen.find(substring) == seen.end()) {
                // Mark it as used
                seen.insert(substring);
                // Recurse from 'end'
                auto candidate = backtrack(s, end, seen);
                int currCount = 1 + candidate.first;
                // Check if this candidate produces a larger count.
                if (currCount > maxCount) {
                    maxCount = currCount;
                    bestSplitting = candidate.second;
                    // Prepend the current substring.
                    bestSplitting.insert(bestSplitting.begin(), substring);
                }
                // Backtrack: remove the substring from seen
                seen.erase(substring);
            }
        }
        return {maxCount, bestSplitting};
    }
};

int main() {
    Solution sol;

    // Example 1:
    string s1 = "goooooogle";
    // Expected (one possible answer): ["g", "o", "oo", "ooo", "gl", "e"]
    vector<string> split1 = sol.maxUniqueSplit(s1);
    cout << "Splitting for \"" << s1 << "\": ";
    for (auto &part : split1) {
        cout << "\"" << part << "\" ";
    }
    cout << "\n";

    // Example 2:
    string s2 = "abccccd";
    // Expected (one possible answer): ["a", "b", "c", "cc", "cd"]
    vector<string> split2 = sol.maxUniqueSplit(s2);
    cout << "Splitting for \"" << s2 << "\": ";
    for (auto &part : split2) {
        cout << "\"" << part << "\" ";
    }
    cout << "\n";

    return 0;
}