Sponsored
Sponsored
This approach uses backtracking to explore all possible partitions of the string into unique substrings. We perform a depth-first search (DFS) that tries to form new substrings starting from each character position. If the substring formed is unique, we recursively call the DFS on the remaining substring. We use a set to track the substrings found so far to ensure all splits are unique.
Time complexity: O(2^n), as for each character, we have a choice of either starting a new substring or extending an existing one.
Space complexity: O(n), for the recursion stack and the set tracking seen substrings.
1#include <unordered_set>
2#include <string>
3#include <algorithm>
4
5int backtrack(const std::string &s, int start, std::unordered_set<std::string> &seen) {
6 if (start == s.length()) return 0;
7 int max_splits = 0;
8 for (int end = start + 1; end <= s.length(); ++end) {
9 std::string sub = s.substr(start, end - start);
10 if (seen.find(sub) == seen.end()) {
11 seen.insert(sub);
12 max_splits = std::max(max_splits, 1 + backtrack(s, end, seen));
13 seen.erase(sub);
14 }
15 }
16 return max_splits;
17}
18
19int maxUniqueSplit(std::string s) {
20 std::unordered_set<std::string> seen;
21 return backtrack(s, 0, seen);
22}This C++ implementation mirrors the Python solution. The helper function backtrack is responsible for attempting to split the string s into unique substrings starting at index start. It uses a set seen to ensure uniqueness of substrings formed during the recursive search. The base case handles when the start reaches the end of the string, indicating all possible splits have been attempted.
This approach uses dynamic programming combined with bit masking to efficiently store unique substrings. With the string's length constraint (≤ 16), each bit in a mask represents whether a character at a position is part of the current substring. This allows us to attempt various splits and ensure uniqueness by tracking substrings in a hash set or array indexed by bit states.
Time complexity: O(2^n * n), accounting for combination checks at each character from the bitmask possibilities.
Space complexity: O(n), handling recursion and storage of current substring states.
1def maxUniqueSplit(s: str) -> int:
2 n
The Python implementation uses a bitmask to track whether a character has been used. dfs iteratively builds substrings and modifies the bitmask to reflect inclusion of new characters. It recursively checks all valid substring combinations for maximum splits by using the current bitmask state as it moves along the input string.