LeetCode Problem 1593

Difficulty: 🟡 Medium
Topics: Hash Table, String, Backtracking

Solution

LeetCode 1593 - Split a String Into the Max Number of Unique Substrings

Problem Understanding

This problem asks us to split a string into the largest possible number of substrings such that every substring is unique. The substrings must be contiguous pieces of the original string, and when combined in order, they must reconstruct the original string exactly.

The key requirement is uniqueness. Once a substring has already been used in the current split, it cannot appear again. The goal is not to find all valid splits, but rather to maximize how many unique substrings we can create.

For example, consider the string "ababccc". One valid split is:

["a", "b", "ab", "c", "cc"]

All substrings are unique, and together they form the original string. The answer is 5 because it is impossible to create more than five unique substrings while satisfying all constraints.

The input consists of a single string s containing only lowercase English letters. The string length is at most 16, which is extremely important. A length this small strongly suggests that an exponential or backtracking based solution is acceptable. Problems with constraints this small are usually designed for recursive exploration of possibilities.

The output is a single integer representing the maximum number of unique substrings achievable.

Several edge cases are important to recognize early:

• A string with all identical characters, such as "aaaa", severely limits the number of unique splits because repeated single character substrings are not allowed.
• A very short string, such as length 1, has only one possible answer.
• Strings with many distinct characters, such as "abcdef", can usually be split into all single character substrings.
• Greedy splitting does not always work. Choosing the shortest substring first may block future valid splits.

Because every possible partition may need to be explored, the problem naturally leads to backtracking with pruning.

Approaches

Brute Force Approach

The brute force solution generates every possible way to split the string and checks whether all resulting substrings are unique.

A string of length n has n - 1 possible split positions. Each position can either contain a cut or not contain a cut, which means there are 2^(n-1) possible partitions overall.

For each partition, we would:

1. Construct all substrings.
2. Insert them into a set.
3. Verify whether duplicates exist.
4. Track the maximum number of unique substrings found.

This approach is correct because it examines every possible split configuration. However, it becomes inefficient because it repeatedly reconstructs partitions and performs duplicate checks after the fact.

Optimal Approach, Backtracking with Pruning

The better solution uses backtracking combined with a hash set.

Instead of generating all partitions first and validating later, we build the split incrementally. At every position, we try all possible substrings starting from the current index. If a substring has not already been used, we add it to the set and continue recursively.

The key optimization is pruning. Suppose we already found a solution with best unique substrings. If the current number of chosen substrings plus the number of remaining characters cannot possibly exceed best, then continuing this branch is pointless.

This pruning dramatically reduces the search space.

Because the maximum string length is only 16, this recursive exploration is fast enough in practice.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(n)	Generates every partition and validates uniqueness afterward
Optimal	O(2^n) worst case	O(n)	Backtracking with pruning and incremental uniqueness checking

Algorithm Walkthrough

1. Initialize a hash set called used_substrings.

This set stores all substrings currently chosen in the active split path. Using a hash set allows constant time uniqueness checks. 2. Maintain a global or external variable called max_count.

This variable tracks the best answer found so far. 3. Create a recursive backtracking function that takes the current index in the string.

The function represents the state where everything before the current index has already been split into unique substrings. 4. If the current index reaches the end of the string, update max_count.

Reaching the end means we formed a complete valid split. 5. Before exploring further, apply pruning.

If:

current_unique_count + remaining_characters <= max_count

then even the best possible continuation cannot improve the answer. In that case, stop exploring this branch. 6. Try every possible substring starting at the current index.

For each ending position:

• Extract the substring.
• Check whether it already exists in used_substrings.

7. If the substring is unique:

• Add it to the set.
• Recursively process the remaining suffix.
• Remove it afterward to backtrack correctly.

8. Continue exploring until all valid partitions have been checked.

Why it works

The algorithm systematically explores every valid partition of the string while enforcing uniqueness immediately during construction. Because every possible substring choice is considered at each position, no valid solution can be missed. The pruning condition only eliminates branches that provably cannot improve the current best answer, so correctness is preserved.

Python Solution

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        used_substrings = set()
        max_count = 0
        n = len(s)

        def backtrack(start: int) -> None:
            nonlocal max_count

            # Complete valid split
            if start == n:
                max_count = max(max_count, len(used_substrings))
                return

            # Pruning
            if len(used_substrings) + (n - start) <= max_count:
                return

            # Try all possible substrings
            for end in range(start + 1, n + 1):
                substring = s[start:end]

                if substring not in used_substrings:
                    used_substrings.add(substring)
                    backtrack(end)
                    used_substrings.remove(substring)

        backtrack(0)
        return max_count

The implementation starts by creating a set called used_substrings, which keeps track of substrings already included in the current split.

The recursive backtrack function processes the string from left to right. The parameter start indicates the next index that still needs to be partitioned.

When start == n, the entire string has been successfully split into unique substrings. At that point, the algorithm updates max_count.

The pruning condition is important for efficiency. Even if every remaining character became its own unique substring, the branch cannot improve the current best answer if the total would still not exceed max_count.

The loop explores every substring beginning at start. If the substring has not already been used, it is temporarily added to the set, recursion continues, and afterward the substring is removed to restore the previous state.

This add-recursively-remove pattern is the standard structure of backtracking algorithms.

Go Solution

func maxUniqueSplit(s string) int {
    usedSubstrings := make(map[string]bool)
    maxCount := 0
    n := len(s)

    var backtrack func(int)

    backtrack = func(start int) {
        // Complete valid split
        if start == n {
            if len(usedSubstrings) > maxCount {
                maxCount = len(usedSubstrings)
            }
            return
        }

        // Pruning
        if len(usedSubstrings)+(n-start) <= maxCount {
            return
        }

        // Try all possible substrings
        for end := start + 1; end <= n; end++ {
            substring := s[start:end]

            if !usedSubstrings[substring] {
                usedSubstrings[substring] = true
                backtrack(end)
                delete(usedSubstrings, substring)
            }
        }
    }

    backtrack(0)
    return maxCount
}

The Go solution follows the same logic as the Python version. Instead of using a set, Go uses a map[string]bool to track used substrings.

Go slices strings using byte indices, which works correctly here because the problem guarantees lowercase English letters only. No Unicode complications exist.

The recursive function is declared using a function variable because Go requires explicit recursive closure declarations.

Integer overflow is not a concern because the maximum answer is at most 16.

Worked Examples

Example 1

Input: s = "ababccc"

Initial state:

Variable	Value
used_substrings	{}
max_count	0

The recursion explores possibilities.

One optimal path:

Step	Current Substring	Set Contents
1	"a"	{"a"}
2	"b"	{"a", "b"}
3	"ab"	{"a", "b", "ab"}
4	"c"	{"a", "b", "ab", "c"}
5	"cc"	{"a", "b", "ab", "c", "cc"}

All characters are consumed.

Variable	Value
max_count	5

The algorithm continues exploring other branches but never finds a better result.

Final answer:

5

Example 2

Input: s = "aba"

Possible exploration:

Step	Current Substring	Set Contents
1	"a"	{"a"}
2	"b"	{"a", "b"}

Remaining string:

"a"

But "a" already exists in the set, so this branch fails.

Another branch:

Step	Current Substring	Set Contents
1	"a"	{"a"}
2	"ba"	{"a", "ba"}

This succeeds with 2 unique substrings.

Final answer:

2

Example 3

Input: s = "aa"

Possible partitions:

Partition	Valid
["a", "a"]	No
["aa"]	Yes

The maximum valid count is 1.

Final answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(2^n) worst case	Backtracking explores many substring partition combinations
Space	O(n)	Recursion depth and hash set storage

The worst case occurs when many different substring combinations are possible, causing the recursion tree to grow exponentially. However, the pruning optimization significantly reduces practical runtime.

The space usage is linear because the recursion depth cannot exceed n, and the set stores at most n substrings.

Test Cases

solution = Solution()

assert solution.maxUniqueSplit("ababccc") == 5  # Provided example
assert solution.maxUniqueSplit("aba") == 2  # Repeated characters
assert solution.maxUniqueSplit("aa") == 1  # Cannot split uniquely

assert solution.maxUniqueSplit("a") == 1  # Single character
assert solution.maxUniqueSplit("abcdef") == 6  # All unique characters
assert solution.maxUniqueSplit("aaaa") == 2  # Requires larger substrings
assert solution.maxUniqueSplit("abca") == 3  # Mixed repeated pattern
assert solution.maxUniqueSplit("wwwzfvedwfvhsww") == 11  # Larger stress case
assert solution.maxUniqueSplit("abcdefghijklmnop") == 16  # Maximum length, all unique
assert solution.maxUniqueSplit("ababab") == 4  # Multiple branching possibilities

Test	Why
"ababccc"	Validates provided example
"aba"	Tests repeated character handling
"aa"	Tests minimal unique splitting
"a"	Smallest possible input
"abcdef"	Every character can be unique
"aaaa"	Forces reuse prevention
"abca"	Tests mixed duplicate patterns
"wwwzfvedwfvhsww"	Larger recursive search space
"abcdefghijklmnop"	Maximum length with ideal splitting
"ababab"	Ensures backtracking explores multiple branches

Edge Cases

Single Character String

A string such as "a" is the smallest valid input. The only possible split is the string itself, so the answer must be 1.

This case can expose bugs in recursion termination logic. The implementation handles it correctly because the recursion immediately reaches the end after selecting the single substring.

All Characters Identical

Consider "aaaa".

A naive greedy approach might try splitting into:

["a", "a", "a", "a"]

However, this violates the uniqueness requirement.

The backtracking solution correctly explores larger substrings such as "aa" or "aaa" and finds the best valid split.

Maximum Length Input

The maximum string length is 16, such as:

"abcdefghijklmnop"

This creates a large search space because many valid partitions exist.

The pruning optimization becomes important here. Without pruning, unnecessary recursive branches would still be explored even after a strong solution had already been found.

The implementation safely handles this case because recursion depth remains small and the pruning condition eliminates many impossible branches.