1593. Split a String Into the Max Number of Unique Substrings

Given a string s, return the maximum number of unique substrings that the given string can be split into.

You can split string s into any list of non-empty substrings, where the concatenation of the substrings forms the original string. However, you must split the substrings such that all of them are unique.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "ababccc"
Output: 5
Explanation: One way to split maximally is ['a', 'b', 'ab', 'c', 'cc']. Splitting like ['a', 'b', 'a', 'b', 'c', 'cc'] is not valid as you have 'a' and 'b' multiple times.

Example 2:

Input: s = "aba"
Output: 2
Explanation: One way to split maximally is ['a', 'ba'].

Example 3:

Input: s = "aa"
Output: 1
Explanation: It is impossible to split the string any further.

Constraints:

• 1 <= s.length <= 16

• s contains only lower case English letters.

Approach 01:

#include <string>
#include <unordered_set>

class Solution {
public:
    int maxUniqueSplit(std::string s) {
        size_t maxUniqueParts = 0;
        findMaxUniqueSplit(s, 0, {}, maxUniqueParts);
        return maxUniqueParts;
    }

private:
    void findMaxUniqueSplit(const std::string& str, int startIndex, std::unordered_set<std::string>&& uniqueSet, size_t& maxUniqueParts) {
        if (startIndex == str.length()) {
            maxUniqueParts = std::max(maxUniqueParts, uniqueSet.size());
            return;
        }

        for (int i = 1; startIndex + i <= str.length(); ++i) {
            const std::string currentPart = str.substr(startIndex, i);
            if (uniqueSet.find(currentPart) != uniqueSet.end())
                continue;
            uniqueSet.insert(currentPart);
            findMaxUniqueSplit(str, startIndex + i, std::move(uniqueSet), maxUniqueParts);
            uniqueSet.erase(currentPart);
        }
    }
};

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        # Use a set to track unique substrings
        return self.findMaxUniqueSplit(s, 0, set())

    def findMaxUniqueSplit(self, s: str, startIndex: int, uniqueSet: set) -> int:
        # If we have processed the entire string, return 0
        if startIndex == len(s):
            return 0

        maxUniqueParts = 0

        # Try all possible splits starting at startIndex
        for i in range(startIndex, len(s)):
            currentPart = s[startIndex:i + 1]  # Substring from startIndex to i
            if currentPart not in uniqueSet:
                uniqueSet.add(currentPart)
                # Recursively split the remaining string and count unique parts
                maxUniqueParts = max(maxUniqueParts, 1 + self.findMaxUniqueSplit(s, i + 1, uniqueSet))
                uniqueSet.remove(currentPart)

        return maxUniqueParts

Time Complexity

• Backtracking Exploration:

  In the worst case, the function explores all possible ways to split the string s. The number of ways to split a string of length n is bounded by \(2^{n-1}\), since each character can either start a new substring or be part of an existing one.

• Checking Substrings:

  For each recursive call, the function generates a substring and checks if it exists in the unordered_set. Generating a substring takes \(O(n)\) time in the worst case, and checking/inserting into the hash set is an average \(O(1)\) operation.

• Overall Time Complexity:

  Considering the exponential number of splits and the cost of checking/creating substrings, the worst-case time complexity is \(O(n \cdot 2^n)\), where n is the length of the input string.

Space Complexity

• Recursive Call Stack:

  The recursive function uses a call stack with depth proportional to the length of the string, leading to a space complexity of \(O(n)\) for the recursive calls.

• Hash Set Storage:

  The unordered_set stores unique substrings generated during recursion. In the worst case, we can have up to \(n\) unique substrings, leading to \(O(n)\) space for the hash set.

• Overall Space Complexity:

  The overall space complexity is \(O(n)\), primarily due to the hash set and the recursive call stack.