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.
1def maxUniqueSplit(s: str) -> int:
2 def backtrack(start, seen):
3 if start == len(s):
4 return 0
5 max_splits = 0
6 for end in range(start + 1, len(s) + 1):
7 sub = s[start:end]
8 if sub not in seen:
9 seen.add(sub)
10 max_splits = max(max_splits, 1 + backtrack(end, seen))
11 seen.remove(sub)
12 return max_splits
13
14 return backtrack(0, set())The function maxUniqueSplit uses a helper backtrack that attempts to partition the given string s starting from an index. The index ranges from the current start position to the end of the string. For each possible substring, it checks its uniqueness by verifying against a set seen. If unique, the substring is added to seen, and the function recurses with the remaining part. The end condition is when the start hits the string's length, meaning no more characters are left to process.
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.