Leetcode Daily Question 21/10/2024 - 1593. Split a String Into the Max Number of Unique Substrings

Problem Description:

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.

class Solution:
  def maxUniqueSplit(self, s: str) -> int:
    def backtrack(start, unique):
      if start == len(s):
        return len(unique)
      
      max_splits = 0
      
      for end in range(start + 1, len(s) + 1):
        curr_word = s[start:end]
        if curr_word not in unique:
          unique.add(curr_word)
          max_splits = max(max_splits, backtrack(end, unique))
          unique.remove(curr_word)
          
      return max_splits
    
    seen = set()
    return backtrack(0, seen)

Explanation:

The idea is to traverse the string, everytime we see a unique element, we add it to a seen set. We then try to take the rest of the string and do the same thing.

If at any point we see the same characters again, we backtrack to the point where we left off and try again by starting with a different combination of characters.

Take "ababccc" as an example.
We observe that "a" has not been seen. Then we try the substring "babccc".

We observe that "b" has not been seen. So we try "abccc". Now since "a" has been seen we backtrack and try "ab" instead.

Then we have "ccc". We observe that "c" has not been seen, so we try "cc".

Since "c" has been seen, we backtrack to determine that "cc" is the only way forward.

So the result would be 5, representing "a", "b" , "ab", "c", and "cc".

def backtrack(start, unique):
  if start == len(s):
    return len(unique)
  
  max_splits = 0
  
  for end in range(start + 1, len(s) + 1):
    curr_string = s[start:end]
    if curr_string not in unique:
      unique.add(curr_string)
      max_splits = max(max_splits, backtrack(end, unique)) # Update the number of splits encountered as we backtrack.
      unique.remove(curr_string)
  return max_splits

The time complexity is O(2^n) since for each character in s, we have two choices, to split or not.

The space complexity is O(1) since we only store constant variables.

The full solution can be found near the top of the page.