# Split a String Into the Max Number of Unique Substrings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/split-a-string-into-the-max-number-of-unique-substrings)
Canonical: https://scaleengineer.com/dsa/problems/split-a-string-into-the-max-number-of-unique-substrings
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** Hash Table, String
---
## Problem
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.

# Approaches
## Brute Force by Generating All Partitions
This method systematically generates every possible partition of the string. A string of length `N` has `N-1` potential positions for a split. We can use a bitmask of length `N-1` to represent a partition: if the `i`-th bit is set, we split the string at index `i`. This results in `2^(N-1)` total partitions. For each partition, we generate the list of substrings, check if they are all unique, and if so, we update the maximum number of substrings found in a valid partition.
**Time:** O(2^N * N), where N is the length of the string. There are `2^(N-1)` possible partitions. For each partition, we spend O(N) time to generate the substrings and check for uniqueness. · **Space:** O(N), where N is the length of the string. We need to store the substrings for one partition at a time. The sum of the lengths of these substrings is always N.
**Pros:** Conceptually simple and straightforward to implement.; Guaranteed to find the correct answer as it explores the entire solution space.
**Cons:** Highly inefficient due to its exponential time complexity.; It generates and checks many complete partitions that are invalid, performing redundant work that could be avoided.
### Explanation
The core idea is to map each integer from `0` to `2^(N-1) - 1` to a unique partition of the string. We iterate through all these integers. For each integer, which acts as a bitmask, we build the corresponding list of substrings. A '1' at bit `j` in the mask signifies a cut after character `j`. After creating a list of substrings for a partition, we check its validity. A partition is valid if all its substrings are unique. This can be easily checked by inserting all substrings into a `HashSet` and comparing the set's size with the list's size. If the partition is valid, we update our global maximum with the number of substrings in this partition. This approach is exhaustive and guarantees finding the optimal solution, but it's inefficient as it explores many invalid partitions from start to finish.

```java
class Solution {
    public int maxUniqueSplit(String s) {
        int n = s.length();
        int maxCount = 0;
        // Iterate through all 2^(n-1) partitions using a bitmask
        for (int i = 0; i < (1 << (n - 1)); i++) {
            List<String> substrings = new ArrayList<>();
            int lastCut = 0;
            for (int j = 0; j < n - 1; j++) {
                // Check if the j-th bit is set, meaning a cut after index j
                if ((i & (1 << j)) != 0) {
                    substrings.add(s.substring(lastCut, j + 1));
                    lastCut = j + 1;
                }
            }
            // Add the last part of the string
            substrings.add(s.substring(lastCut));

            // Check for uniqueness
            Set<String> uniqueSubstrings = new HashSet<>(substrings);
            if (uniqueSubstrings.size() == substrings.size()) {
                maxCount = Math.max(maxCount, substrings.size());
            }
        }
        // If n > 0, maxCount will be at least 1 (the string itself)
        return maxCount;
    }
}
```
### Algorithm
- Initialize `max_splits = 1`.
- Let `N` be the length of the string `s`.
- Iterate through a `mask` from `0` to `2^(N-1) - 1`. Each `mask` represents a unique partition.
- For each `mask`, generate the corresponding partition:
  - Create an empty list `parts` to store substrings.
  - Initialize `last_cut_index = 0`.
  - Iterate `j` from `0` to `N-2`:
    - If the `j`-th bit of the `mask` is `1`, it signifies a cut after character `j`.
    - Add `s.substring(last_cut_index, j + 1)` to `parts`.
    - Update `last_cut_index = j + 1`.
  - Add the final substring `s.substring(last_cut_index)` to `parts`.
- Check for uniqueness:
  - Create a `HashSet` from the `parts` list.
  - If the size of the set is equal to the size of the `parts` list, the partition is valid.
  - Update `max_splits = max(max_splits, parts.size())`.
- Return `max_splits`.

## Backtracking with Pruning
A more efficient approach is to use backtracking with recursion. Instead of generating a full partition and then checking its validity, we build a valid partition incrementally. We explore potential splits, and if a split leads to a duplicate substring, we immediately abandon that path (a technique called pruning) and backtrack to try a different split. This avoids a significant amount of redundant computation compared to the brute-force method.
**Time:** O(2^N * N). In the worst case, the number of valid partitions can be exponential. The N factor comes from substring creation and set operations within the recursion. While the worst-case complexity is the same as brute force, pruning makes it significantly faster on average. · **Space:** O(N), where N is the length of the string. The recursion depth can go up to N, consuming O(N) stack space. The `HashSet` also stores substrings whose total length is N, taking O(N) space.
**Pros:** Significantly more efficient in practice than the brute-force approach due to pruning of invalid search paths.; Guaranteed to find the optimal solution by exploring all valid possibilities.
**Cons:** The time complexity is still exponential in the worst-case scenario.; Recursion can lead to stack overflow for very large N, though not an issue with the given constraints (N <= 16).
### Explanation
We define a recursive function that tries to extend a valid partial split. The state of our recursion includes the starting index for the next substring and the set of unique substrings found so far in the current path.

The function `backtrack(index, currentSet)` works as follows:
- **Base Case:** If `index` reaches the end of the string, it means we've found a valid partition of the entire string. We update our global maximum with the number of substrings in `currentSet`.
- **Recursive Step:** We iterate from the current `index` to the end of the string. In each iteration `i`, we form a new substring `sub = s.substring(index, i + 1)`. If `sub` is not already in our `currentSet`, we've found a potential unique substring. We add it to the set and make a recursive call for the rest of the string: `backtrack(i + 1, currentSet)`. After the recursive call returns, we must backtrack by removing `sub` from `currentSet`. This allows us to explore other partitions, for example, by taking a longer substring starting at `index`. This "choose-explore-unchoose" pattern is the essence of backtracking and ensures all valid partitions are explored systematically.

```java
class Solution {
    int maxCount = 0;

    public int maxUniqueSplit(String s) {
        backtrack(s, 0, new HashSet<>());
        return maxCount;
    }

    private void backtrack(String s, int index, Set<String> currentSet) {
        // Base case: we have successfully split the entire string
        if (index == s.length()) {
            maxCount = Math.max(maxCount, currentSet.size());
            return;
        }

        // Optional Pruning: if we can't possibly beat the current max, stop.
        // At best, the rest of the string can be split into s.length() - index single characters.
        if (currentSet.size() + (s.length() - index) <= maxCount) {
            return;
        }

        // Recursive step: try all possible splits from the current index
        for (int i = index; i < s.length(); i++) {
            String sub = s.substring(index, i + 1);
            if (!currentSet.contains(sub)) {
                // Choose
                currentSet.add(sub);
                // Explore
                backtrack(s, i + 1, currentSet);
                // Unchoose (backtrack)
                currentSet.remove(sub);
            }
        }
    }
}
```
### Algorithm
- Initialize a global variable `max_splits = 0`.
- Define a recursive function `backtrack(s, index, current_set)`.
  - `s`: The input string.
  - `index`: The starting index for the next potential substring.
  - `current_set`: A `HashSet` storing unique substrings in the current partition path.
- **Base Case**: If `index` equals `s.length()`, we have successfully partitioned the whole string.
  - Update `max_splits = max(max_splits, current_set.size())`.
  - Return.
- **Recursive Step**: Iterate `i` from `index` to `s.length() - 1`.
  - Create a substring `sub = s.substring(index, i + 1)`.
  - If `sub` is not in `current_set`:
    - **Choose**: Add `sub` to `current_set`.
    - **Explore**: Call `backtrack(s, i + 1, current_set)`.
    - **Unchoose**: Remove `sub` from `current_set` to backtrack and explore other possibilities.
- Start the process by calling `backtrack(s, 0, new HashSet<>())`.
- Return `max_splits`.

# Solutions
### Java

```java
class Solution {
private
  Set<String> vis = new HashSet<>();
private
  int ans = 1;
private
  String s;
public
  int maxUniqueSplit(String s) {
    this.s = s;
    dfs(0, 0);
    return ans;
  }
private
  void dfs(int i, int t) {
    if (i >= s.length()) {
      ans = Math.max(ans, t);
      return;
    }
    for (int j = i + 1; j <= s.length(); ++j) {
      String x = s.substring(i, j);
      if (vis.add(x)) {
        dfs(j, t + 1);
        vis.remove(x);
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  unordered_set<string> vis;
  string s;
  int ans = 1;
  int maxUniqueSplit(string s) {
    this->s = s;
    dfs(0, 0);
    return ans;
  }
  void dfs(int i, int t) {
    if (i >= s.size()) {
      ans = max(ans, t);
      return;
    }
    for (int j = i + 1; j <= s.size(); ++j) {
      string x = s.substr(i, j - i);
      if (!vis.count(x)) {
        vis.insert(x);
        dfs(j, t + 1);
        vis.erase(x);
      }
    }
  }
};

```

### Python

```python
class Solution:
    def maxUniqueSplit(self, s: str) -> int: def dfs(i, t): if i >= len(s): nonlocal ans ans = max(ans, t) return for j in range(i + 1, len(s) + 1): if s[i: j] not in vis: vis . add(s[i: j]) dfs(j, t + 1) vis . remove(s[i: j]) vis = set() ans = 1 dfs(0, 0) return ans

```