0% completed

Split a String Into the Max Number of Unique Substrings (medium)

Problem Statement

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 = "aab"  
Output: 2

.....

Like the course? Get enrolled and start learning!

U

Utkarsh Gupta

· 3 years ago

Show 2 replies

M

Mudassir Maredia

· 2 years ago

Input: s = "abcabc"  
Output: 4  
Explanation: Four possible ways to split into maximum unique substrings are: ['a', 'b', 'c', 'abc'] & ['a', 'b', 'cab', 'c'] &  ['a', 'bca', 'b', 'c'] & ['abc', 'a', 'b', 'c'], all have 4 substrings.

Other than 4 combinations listed in Example:2, why can't following be the possibilities as well ?

['abcab', 'c']
['abca', 'bc']
['ab', 'cabc']
['a', 'bcabc']

Show 1 reply

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def maxUniqueSplit(self, s: str) -> int:
    
    def backtrack(s, seen, index):
      if index == len(s):
        return len(seen)

      max_split = 0        
    
      # from: index + 1 as we want to start from the index to --> any possible next character 
      # to: len(s) + 1 because s[start: end] the syntax in not inclusive to the end  
      for i in range(index + 1, len(s) + 1):
        substring = s[index: i]
        if substring not in seen:
          seen.add(substring)
          max_split = max(max_split, backtrack(s, seen, i))
          seen.remove(substring)
      
      return max_split
    
    return backtrack(s, set(), 0)

M

mailman14736

· 2 months ago