Max unique splits

XXX. Max Unique Split

Backtracking

Set

Problem Statement:

Given a string s, split it into substrings such that all the substrings are unique. Return the maximum number of unique substrings that can be achieved.

Algorithm:

This problem can be solved using backtracking:

1. Use a set to keep track of substrings that have already been seen to ensure uniqueness.
2. Start with an empty substring and recursively explore all possible substrings starting from the current index.
3. For each substring:
   • If it has not been seen before, add it to the set and recursively try to split the remaining part of the string.
   • After the recursive call, backtrack by removing the substring from the set.
4. Keep track of the maximum count of unique substrings encountered during the recursion.

Complexity:

Time Complexity: O(2ⁿ), where n is the length of the string. Each substring can be either included or not.
Space Complexity: O(n), for the recursion stack and the set of seen substrings.

Java Implementation:

public class Solution {
    public int maxUniqueSplit(String s) {
        Set seen = new HashSet<>();
        int[] maxCount = new int[1];
        backtrack(s, 0, seen, 0, maxCount);
        return maxCount[0];
    }

    private void backtrack(String s, int start, Set seen, int count, int[] maxCount) {
        // Prune: If the current count plus remaining characters can't exceed maxCount, return
        if (count + (s.length() - start) <= maxCount[0]) return;

        // Base case: If we reach the end of the string, update maxCount
        if (start == s.length()) {
            maxCount[0] = Math.max(maxCount[0], count);
            return;
        }

        // Try every possible substring starting from 'start'
        for (int end = start + 1; end <= s.length(); ++end) {
            String substring = s.substring(start, end);
            // If the substring is unique
            if (!seen.contains(substring)) {
                // Add the substring to the seen set
                seen.add(substring);
                // Recursively count unique substrings from the next position
                backtrack(s, end, seen, count + 1, maxCount);
                // Backtrack: remove the substring from the seen set
                seen.remove(substring);
            }
        }
    }
}