#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;
}