Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Split a String Into the Max Number of Unique Substrings

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 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)
A

Anonymous

· 3 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
A

Anonymous

· 3 years ago

How come the time complexity is 2^n? Should it be 2 ^ (n*n) ?

Show 2 replies

Reading Progress

0%

Vote for new content