Problem of The Day: Split a String Into the Max Number of Unique Substrings

Problem Statement

Intuition

When I first looked at the problem, I thought about splitting the string in different ways to maximize the number of unique substrings. The challenge was to try out all possible splits and ensure that each split part was unique.

Approach

I used backtracking to solve this problem. Backtracking helps me explore all possible ways to split the string and check if the substrings are unique.

Here’s what happens:

• I start at the beginning of the string and try to split it at every position.
• For each possible substring, I check if it’s already in the set of unique substrings. If it is not, I add it to the set and continue trying to split the remaining part of the string.
• If I reach the end of the string, I check how many unique substrings I’ve found so far and update my result if it’s the maximum.
• After trying all possibilities, I return the result which is the maximum number of unique substrings I can achieve.

Complexity

• Time complexity: The time complexity is \(O(2^n)\) because at each character, I have two choices: either include it in the current substring or start a new substring. This leads to exponential growth in possible combinations.

• Space complexity: The space complexity is \(O(n)\) because the space used is proportional to the length of the string, mainly for storing the set of unique substrings.

Code

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        unique_strings = set()
        N = len(s)
        self.res = 0
        def backtrack(i, track_set):
            if i == N:
                self.res = max(self.res, len(track_set))
                return
            for j in range(i, N):
                if s[i:j + 1] in track_set:
                    continue
                track_set.add(s[i:j+1])
                split = backtrack(j + 1, track_set)
                track_set.remove(s[i:j + 1])

        backtrack(0, unique_strings)
        return self.res

Editorial

Approach 1: Backtracking

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        seen = set()
        return self.backtrack(s, 0, seen)

    def backtrack(self, s, start, seen):
        if start == len(s):
            return 0

        max_count = 0

        for end in range(start + 1, len(s) + 1):
            sub_string = s[start:end]
            if sub_string not in seen:
                seen.add(sub_string)
                max_count = max(max_count, 1 + self.backtrack(s, end, seen))
                seen.remove(sub_string)

        return max_count

Approach 2: Backtracking with Pruning

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        seen = set()
        max_count = [0]
        self.backtrack(s, 0, seen, 0, max_count)
        return max_count[0]

    def backtrack(
        self, s: str, start: int, seen: set, count: int, max_count: list
    ) -> None:
        if count + (len(s) - start) <= max_count[0]:
            return
        if start == len(s):
            max_count[0] = max(max_count[0], count)
            return
        for end in range(start + 1, len(s) + 1):
            sub_string = s[start:end]
            if sub_string not in seen:
                seen.add(sub_string)
                self.backtrack(s, end, seen, count + 1, max_count)
                seen.remove(sub_string)
        return

• time: O(n2^n)
• space: O(n)