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.
1const maxUniqueSplit = function(s) {
2 const backtrack = (start, seen) => {
3 if (start === s.length) return 0;
4 let maxSplits = 0;
5 for (let end = start + 1; end <= s.length; end++) {
6 const sub = s.slice(start, end);
7 if (!seen.has(sub)) {
8 seen.add(sub);
9 maxSplits = Math.max(maxSplits, 1 + backtrack(end, seen));
10 seen.delete(sub);
11 }
12 }
13 return maxSplits;
14 };
15
16 return backtrack(0, new Set());
17};The JavaScript function uses a similar approach with a Set for tracking unique substrings and a recursive helper backtrack to manage starting points. It iterates through potential substring partitions, ensuring no duplicates by checking the Set.
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.