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.
1import java.util.HashSet;
2
3public class MaxUniqueSplit {
4 public int maxUniqueSplit(String s) {
5 return backtrack(s, 0, new HashSet<>());
6 }
7
8 private int backtrack(String s, int start, HashSet<String> seen) {
9 if (start == s.length()) return 0;
10 int maxSplits = 0;
11 for (int end = start + 1; end <= s.length(); end++) {
12 String sub = s.substring(start, end);
13 if (!seen.contains(sub)) {
14 seen.add(sub);
15 maxSplits = Math.max(maxSplits, 1 + backtrack(s, end, seen));
16 seen.remove(sub);
17 }
18 }
19 return maxSplits;
20 }
21}The Java solution implements the same backtracking strategy and checks for substring uniqueness using a HashSet seen. Each recursive call tries to find the maximum unique splits from the current start index until the end is reached, backtracking if reuse of a substring is detected.
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.