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 = "ababccc"
Output: 5
Explanation: One way to split maximally is ['a', 'b', 'ab', 'c', 'cc']. Splitting like ['a', 'b', 'a', 'b', 'c', 'cc'] is not valid as you have 'a' and 'b' multiple times.

Example 2:
Input: s = "aba"
Output: 2
Explanation: One way to split maximally is ['a', 'ba'].

Example 3:
Input: s = "aa"
Output: 1
Explanation: It is impossible to split the string any further.

 
Constraints:


1 <= s.length <= 16


s contains only lower case English letters.

Difficulty: interview

Starter code:

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        

Solutions:
class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        self.x, n = 0, len(s)
        def maxUniqueSplit_(i=0, S=set()):
            if s[i:] not in S:
                self.x = max(self.x, len(S) + 1)
            
            for j in range(i + 1, n):
                if s[i : j] not in S and len(S) + 1 + n - j > self.x:
                    maxUniqueSplit_(j, S.union({s[i : j]}))
            
        
        maxUniqueSplit_()
        return self.x

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        start = 0
        end = 0
        se = set()
        res = 0
        def helper(stn, se, count):
            nonlocal res
            if not stn:
                res = max(res, count)
            if len(stn) + count <= res:
                return
            for i in range(1, len(stn)+1):
                if stn[:i] not in se:
                    helper(stn[i:], se|{stn[:i]}, count + 1)
        helper(s, se, 0)
        return res
            


class Solution:
    def maxUniqueSplit(self, s: str, mem=None, seen=None) -> int:
        if mem is None:
          mem={}
        if seen is None:
          seen = set()
        
        res = 0
        for i in range(0, len(s)):
          if s[0:i+1] in seen:
            continue
          seen.add(s[0:i+1])
          res = max(res, 1 + self.maxUniqueSplit(s[i + 1:], mem, seen))
          seen.remove(s[0:i+1])
        mem[s] = res
        
        return res

class Solution:
    
    def func(self, s, idx, words):
        max_result = 0
        for i in range(idx+1, len(s)):
            max_result = max(max_result, self.func(s, i, words|{s[idx:i]}))
        max_result = max(max_result, len(words|{s[idx:]}))
        return max_result
            
    
    def maxUniqueSplit(self, s: str) -> int:
        return self.func(s, 0, set())
        


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        #@functools.lru_cache(None)
        def helper(start):
            if len(s[start:]) == 0: return 0
            res = -math.inf
            for i in range(start+1,len(s)+1):
                if s[start:i] not in seen:
                    seen.add(s[start:i])
                    #print('seen',seen)
                    followup = helper(i)
                    res= max(res,1+followup)
                    #print('results',results,followup,len(seen),seen)
                    seen.remove(s[start:i])
            
            return res
        
        seen = set()
        return helper(0)
        


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

        for i in range(1, n + 1):
            current = s[:i]
            if current not in self.splits:
                self.splits.add(current)
                result = max(result, 1 + self.maxUniqueSplit(s[i:]))
                self.splits.remove(current)

        return result


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        if not s:
            return 0
        splits = [[] for _ in range(len(s))]
        best_len = 0
        for i, c in enumerate(s):
            splits[i].append(set([s[:i + 1]]))
            best_len = max(best_len, 1)
            for j in range(1, i + 1):
                ss = s[j: i + 1]
                for spl in splits[j - 1]:
                    if ss not in spl:
                        best_len = max(best_len, len(spl) + 1)
                        splits[i].append(spl | set([ss]))
        return best_len

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        
        
        def rec(i, myset):
            if i == len(s):
                return 0
            ans = -float('inf')
            for j in range(i, len(s)):
                if s[i:j + 1] not in myset:
                    ans = max(ans, 1 + rec(j + 1, myset | set([s[i:j + 1]])))
            return ans
        return rec(0, set())

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        best_ans = 1
        cur_ans = set()
        
        def find_result(i):
            nonlocal best_ans
            if i >= len(s):
                return len(cur_ans)
            elif len(s) - i + len(cur_ans) < best_ans:
                return best_ans
            
            for j in range(i+1, len(s)+1):
                substr = s[i:j]
                if substr not in cur_ans:
                    cur_ans.add(substr)
                    best_ans = max(best_ans, find_result(j))
                    cur_ans.remove(substr)
            
            return max(best_ans, len(cur_ans))
        
        return find_result(0)
                
                    
            
            


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        lookup = set()
        return self.traverse(s, 0, lookup)
    
    def traverse(self, s, index, lookup):
        if index > len(s):
            return 0
        array = []
        for idx in range(index,len(s)+1):
            if len(s[index:idx])> 0 and s[index:idx] not in lookup:
                lookup.add(s[index:idx])
                array.append(1 + self.traverse(s, idx, lookup))
                lookup.remove(s[index:idx])
                
                
        return max(array)  if array else 0

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def bitsoncount(x):
            return bin(x).count('1')
        
        ans = 0
        n = len(s)
        seen = defaultdict(int)
        for m in range(1<<n):
            if (bitsoncount(m) <= ans): 
                continue
            prev = 0
            count = 0
            for i in range(n):
                if m & (1<<i):
                    sub = s[prev:i+1]
                    prev = i+1
                    if sub not in seen:
                        seen[sub] += 1
                        count += 1
            
            ans = max(ans, count)
            seen.clear()
        
        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        result = []
        
        def dfs(path, word):
            if not word: 
                result.append(path)
                return
            for i in range(1, len(word)+1):
                prefix, suffix = word[:i], word[i:]
                if prefix not in path:
                    dfs(path | {prefix}, suffix)
        
        dfs(set(), s)
        l = 1
        for item in result:
            l = max(len(item), l)
        return l
            


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        n = len(s)
        def dp(cur, ss):
            if cur == n-1:
                return len(set(ss.split()))
            cur += 1
            return max(dp(cur, ss + s[cur]), dp(cur, ss + ' ' + s[cur]))
        return dp(0, s[0])

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        used = set()
        self.res = 1
        self.backtrack(s, 0, used)
        return self.res
    
    def backtrack(self, s, cur, used):
        if not s:
            self.res = max(self.res, cur)
            return
        for i in range(1, len(s)+1):
            if s[:i] not in used:
                used.add(s[:i])
                self.backtrack(s[i:], cur+1, used)
                used.remove(s[:i])

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n = len(s)
        self.res = 0
        
        
        def dfs(strs, s):
            if not s:
                if len(set(strs)) == len(strs):
                    self.res = max(self.res, len(strs))
                return
            dfs(strs + [s[0]], s[1:])
            
            if strs:
                dfs(strs[:-1] + [strs[-1] + s[:1]], s[1:])
            
            
            return
        
        dfs([], s)
        
        return self.res

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def helper(s, seen=set()):
            maximum = 0
            for i in range(1, len(s) + 1):
                candidate = s[:i]
                if candidate not in seen:
                    maximum = max(maximum, 1 + helper(s[i:], {candidate, *seen}))
            return maximum
        return helper(s)


# 1593. Split a String Into the max Number of Unique Substrings

def walk_divisions (string, covered, cut):
    if cut == len (string):
        yield len (covered)
    else:
        for nxt in range (cut + 1, len (string) + 1):
            substring = string[cut : nxt]
            if substring not in covered:
                covered.append (substring)
                yield from walk_divisions (string, covered, nxt)
                covered.pop ()

def max_unique_split (string):
    if len (string) == 1:
        return 1

    assert len (string) >= 2

    return max (walk_divisions (string, [], 0))

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        return max_unique_split(s)

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n = len(s) 
        def dp(i, cur):
            nonlocal ans            
            if len(cur) + n-i < ans: return
            if i >= n: ans = max(ans, len(cur))                
            l = n-i
            for k in range(1, l+1):
                if s[i:i+k] not in cur: 
                    cur.append(s[i:i+k])
                    dp(i+k, cur)
                    cur.pop()            
        ans, cur = 0, []
        dp(0, cur)
        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        prev = [[s[0]]]
        for elm in s[1:]:
            current = []
            for sub in prev:
                copy = list(sub)
                copy[-1] = copy[-1] + elm
                current.append(copy)
                
                copy = list(sub)
                copy.append(elm)
                current.append(copy)
                
            prev = current
            
        return max(len(set(combo)) for combo in prev)


class Solution:
    def maxUniqueSplit(self, s: str, seen=()):
        maximum = 0
        if s:
            for i in range(1, len(s) + 1):
                candidate = s[:i]
                if candidate not in seen:
                    maximum = max(maximum, 1 + Solution.maxUniqueSplit(self, s[i:], {candidate, *seen}))
        return maximum

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        self.maxsplits = 0
        
        def DFS(i, substring_set):
            if i == len(s):
                self.maxsplits = max(len(substring_set), self.maxsplits)
                return

            for j in range(i + 1, len(s) + 1):
                DFS(j, substring_set | {s[i: j]})

        DFS(0, set())
        return self.maxsplits


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        have = set()
        self.cur = []
        
        def dfs(i):
            if i == len(s):
                return 0 if ''.join(self.cur) not in have else -float('inf')
            
            self.cur.append(s[i])
            ret = dfs(i + 1)
            
            st = ''.join(self.cur)            
            if st not in have:
                tmp, self.cur = self.cur, []
                have.add(st)
                ret = max(dfs(i + 1) + 1, ret)
                have.remove(st)
                self.cur = tmp
                
            self.cur.pop()
            return ret
            
        return dfs(0)

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

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        exist = collections.defaultdict(int)
        self.result = 0
        n = len(s)
        def dfs(index:int) -> None:
            # print(exist, index)
            if (index == n):
                self.result = max(self.result, len(exist))
                return
            for i in range(index + 1, n + 1):
                st = s[index:i]
                exist[st] += 1
                dfs(i)
                exist[st] -= 1
                if (exist[st] == 0):
                    del exist[st]
        dfs(0)
        
        return self.result

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n=len(s)
        maxi=0
        
        def sub(ind,ar):
            if(ind==n):
                if(len(ar)==len(set(ar))):
                    return len(ar)
                return maxi
            a=ar+[s[ind]]
            b=ar[:]
            b[-1]+=s[ind]
            
            return max(sub(ind+1,a),sub(ind+1,b))
        return sub(1,[s[0]])
            


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        self.res = 0
        partition = []
        def backtrack(start_i):
            if start_i == len(s):
                self.res = max(self.res, len(set(partition)))
            else:
                for j in range(start_i + 1, len(s) + 1):
                    partition.append(s[start_i:j])
                    backtrack(j)
                    partition.pop()
        backtrack(0)
        return self.res

class Solution:
    def _dfs(self, s, i, visited):
        if i == len(s):
            yield len(visited)
            return
        
        for j in range(i + 1, len(s) + 1):
            if s[i:j] not in visited:
                visited.add(s[i:j])
                yield from self._dfs(s, j, visited)
                visited.remove(s[i:j])
        
    def maxUniqueSplit(self, s: str) -> int:
        if not s:
            return 0
        
        return max(self._dfs(s, 0, set()))

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def dfs(s, path):
            res = 0
            if not s: return len(path)
            for i in range(1,len(s)+1):
                res = max(res, dfs(s[i:],path|{s[:i]}))
            return res
        return dfs(s,set())

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
    
    
        res = 1

        def dfs(pos, path):
            nonlocal res
            if pos == len(s):
                res = max(res, len(set(path)))

            for i in range(pos + 1, len(s) + 1):
                path.append(s[pos: i])
                dfs(i, path)
                path.pop()

        dfs(0, [])
        return res

class Solution:        
    def maxUniqueSplit(self, s: str) -> int:
        if not s:
            return 0
        
        self.answer = 0
        substrings = []
        def backtrack(start_i):
            if start_i == len(s):
                self.answer = max(self.answer, len(set(substrings)))
                return
            for j in range(start_i+1, len(s)+1):
                substrings.append(s[start_i:j])
                backtrack(j)
                substrings.pop()

        backtrack(0)
        return self.answer


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        return self.bt(s, set(), 0, 0)
    
   
    def bt(self, s, d, l, maxl): 
        if l >= len(s):
            maxl = max(len(d), maxl)
            return maxl
        else:
            for r in range(l+1,len(s)+1):  
                if s[l:r] not in d:   # before put the current stage into your dictionary, make sure it meet the condition. 
                    d.add(s[l:r])     # then, you have two choices: put 
                    maxl=self.bt(s, d, r, maxl)
                    d.remove(s[l:r])   # the other choice is not put. (add, then remove)
            return maxl

class Solution:
    
    def maxUniqueSplit(self, s: str) -> int:
        res = 1

        def dfs(pos, path):
            
            nonlocal res
            if pos == len(s):
                #print(path)
                res = max(res, len(set(path)))

            for i in range(pos + 1, len(s) + 1):
                path.append(s[pos: i])
                dfs(i, path)
                path.pop()

        dfs(0, [])
        return res

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def solve(S, subs):
            if not S:
                return len(subs)
            
            ans = 0
            for i in range(len(S)):
                sub = S[:i+1]
                ans = max(ans, solve(S[i+1:], subs | {sub}))
                
            return ans
        return solve(s, set())


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n = len(s) 
        @lru_cache(None)
        def dp(i, cur):
            nonlocal ans            
            if len(cur) + n-i < ans: return
            if i >= n: ans = max(ans, len(cur))                
            l = n-i
            for k in range(1, l+1):
                cand = s[i:i+k]
                if cand not in cur:                     
                    dp(i+k, cur + (cand,))                         
        ans, cur = 0, ()
        dp(0, cur)
        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        self._s = s
        self.best = 1

        self.solve(0, set(), 0)
        return self.best
    
    def solve(self, index, seen, count):
        s = self._s

        if index >= len(s):
            self.best = max(self.best, count)
        
        for end in range(index+1, len(s)+1):
            if s[index:end] not in seen:
                seen.add(s[index:end])
                self.solve(end, seen, count+1)
                seen.remove(s[index:end])



class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        if not s:
            return 0
        return self.dfs(s, set())

    def dfs(self, s: str, present: set) -> int:
        maximum = 0

        for i in range(1, len(s) + 1):
            substring = s[:i]
            if substring not in present:
                sub_try = self.dfs(s[i:], {*present, substring})
                maximum = max(maximum, 1+sub_try)
        return maximum


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        
        
        
        n = len(s)
        def dp(cur, ss):
            # print(ss)
            if cur == n-1:
                return len(set(ss.split()))
            cur += 1
            return max(dp(cur, ss + s[cur]), dp(cur, ss + ' ' + s[cur]))
        return dp(0, s[0])

class Solution:
    def __init__(self):
        self.result = 0

    def maxUniqueSplit(self, s: str) -> int:
        if not s:
          return 0
        def backtrack(start, cur):
            if start == len(s):
                self.result = max(self.result, len(set(cur)))
                return

            for i in range(start, len(s)):
                cur += [s[start:i+1]]
                backtrack(i + 1, cur)
                cur.pop()

        backtrack(0, [])

        return self.result

class Solution:
    def max_unique_substrings(self, s, seen=()):
        maximum = 0
        for i in range(1, len(s) + 1):
            candidate = s[:i]
            if candidate not in seen:
                maximum = max(maximum, 1 + self.max_unique_substrings(s[i:], {candidate, *seen}))
        return maximum
    def maxUniqueSplit(self, s: str) -> int:
        return self.max_unique_substrings(s)

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        res = 1

        def dfs(pos, path):
            nonlocal res
            if pos == len(s):
                res = max(res, len(set(path)))

            for i in range(pos + 1, len(s) + 1):
                path.append(s[pos: i])
                dfs(i, path)
                path.pop()

        dfs(0, [])
        return res


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        res = 0
        def dfs(cur_pos):
            nonlocal res
            if cur_pos == len(s):
                res = max(res, len(seen))
            for next_pos in range(cur_pos, len(s)):
                if s[cur_pos:next_pos + 1] not in seen:
                    seen.add(s[cur_pos:next_pos + 1])
                    dfs(next_pos + 1)
                    seen.remove(s[cur_pos:next_pos + 1])
        
        seen = set()
        dfs(0)
        return res


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        def helper(i,s,seen):
            if i > len(s)-1:
                return len(seen)
            max_len = 1
            for k in range(i,len(s)):
                temp = set(seen)
                temp.add(s[i:k+1])
                max_len = max(max_len, helper(k+1, s,temp))
            return max_len
        return helper(0,s,set([]))


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        if not s:
            return 0
        self. res = 0
        stack = []
        
        def backtrack(ind):
            if ind == len(s):
                self.res = max(self.res, len(set(stack)))
            
            for i in range(ind+1, len(s)+1):
                stack.append(s[ind:i])
                backtrack(i)
                stack.pop()
        backtrack(0)
        return self.res


class Solution:
  def maxUniqueSplit(self, s: str) -> int:
    
    self.ans=1
    def rec(split, s):
      #print(split,s)
      if not s:
        se=set(split)
        if len(se)==len(split):
          self.ans=max(self.ans,len(split))
        return
      
      
      for i in range(len(s)):
        piece=s[0:i+1]
        spl=split[:]
        spl.append(piece)
        rec(spl,s[i+1:])
    
    rec([],s)
    return self.ans

from itertools import combinations
from math import ceil

class Solution:
    
    def maxUniqueSplit(self, s: str) -> int:
        
        l, r = 1, len(s)
        
        def check(n):
            
            if n == 1: return True
            
            pos = [i + 1 for i in range(len(s) - 1)]
            
            for dividers in combinations(pos, n - 1):
                
                i = 0
                words = set()
                flag = 0
                for p in dividers:
                    if s[i: p] in words:
                        flag = 1
                        break
                    words.add(s[i: p])
                    i = p
                    
                if not flag and s[i: len(s)] not in words: 
                    return True
                          
            return False 
        
        while l < r:
            
            mid = l + (r - l) // 2 + 1
            
            if check(mid):
                l = mid
            else:
                r = mid - 1
        
        return r
        
        
        
        


class Solution:
    max_=0
    def maxUniqueSplit(self, s: str) -> int:
        b=len(s)-1
        ar=[]
        self.h(s,b,ar)
        return self.max_
    def h(self,s,b,ar):
        ar2=ar.copy()
        if(b<0):
            self.max_=max(self.max_,len(ar2))
            return 0
        t=s[b:]
        self.h(s,b-1,ar2)
        s=s[:b]
                
        if(t not in ar2):
            ar2.append(t)
            self.h(s,b-1,ar2)
    


class Solution:
    def maxUniqueSplit(self, s: str) -> int:

        if len(s) == 1:
            return 1

        ltrs = set(list(s))

        counts = {}
        for ltr in ltrs:
            counts[ltr] = s.count(ltr)

        unique_count = 0
        for ltr, count in list(counts.items()):
            if count == 1:
                index = s.index(ltr)
                if index == 0 or index == len(s)-1:
                    s = s.replace(ltr,'')
                    unique_count = unique_count + 1
                else:
                    prev = s[index-1]
                    next = s[index+1]
                    if counts[prev] == 1 and counts[next] == 1:
                        s = s.replace(ltr, '')
                        unique_count = unique_count + 1

        if len(s) == 0:
            return unique_count
        else:
            return unique_count + self.find_max(len(s)-1, s)

    def find_max(self, i, s):
        from sortedcontainers import SortedSet

        unique, unique_count = False, -1
        words = s.split()
        if len(words) == len(set(words)):
            unique_count = len(words)

        if i == 0:
            return unique_count

        a = self.find_max(i-1, s[:i] + ' ' + s[i:])
        b = self.find_max(i-1, s)

        return max(a,b,unique_count)


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        seen = set()
        
        def dfs(s, seen=seen):
            if not s:
                return 0
            res = 0
            for i in range(1, len(s)+1):
                if s[:i] in seen:
                    continue
                seen.add(s[:i])
                res = max(res, 1 + dfs(s[i:]))
                seen.remove(s[:i])
            return res
        
        return dfs(s)

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        self.s = s
        self.cache = {}
        count = self.maxUniqueSplitHelper(0, set())
        
        return count
    
    def maxUniqueSplitHelper(self, pos: int, substrings: set) -> int:
        hashed = frozenset(substrings)
        if (pos, hashed) in self.cache:
            return self.cache[(pos, hashed)]
        
        if pos == len(self.s):
            return len(substrings)
        
        count = 0
        for i in range(pos, len(self.s)):
            substring = self.s[pos:i + 1]
            if substring in substrings:
                continue
                
            substrings.add(substring)
            count=max(count, self.maxUniqueSplitHelper(i + 1, substrings))
            substrings.remove(substring)
            
        self.cache[(pos, hashed)] = count
        return count

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        max_len=[1]
        def helper(i,s,vis):
            if i==len(s) and i!=s:
                max_len[0]=max(max_len[0],len(vis))
                return
            j=i
            while j<len(s):
                if s[i:j+1] not in vis and s[i:j+1]!=s:
                    vis[s[i:j+1]]=1
                    helper(j+1,s,vis)
                    del vis[s[i:j+1]]
                j+=1

        helper(0,s,{})
        return  max_len[0]


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        if not s:
            return 0
        
        cache = [None] * len(s)
        
        setSet = (self.dp(s, 0, cache))
        return len(max(setSet, key=lambda x: len(x))) if setSet else 0
    
    def dp(self, inputStr, i, cache):
        if i == len(inputStr):
            return [set()]
        
        if cache[i] is not None:
            return cache[i]
        
        end = len(inputStr) +1
        
        res = set()
        for j in range(i+1, end):
            tempSol = self.dp(inputStr, j, cache)
            
            for substrArr in tempSol:
                if inputStr[i:j] in substrArr:
                    continue

                combined = set(substrArr)
                combined.add(inputStr[i:j])
                res.add(frozenset(combined))
        
        cache[i] = frozenset(res)
        #print(cache[i])
        return cache[i]
                    
            
        


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def helper(s, seen):
            return max((1 + helper(s[i:], {candidate, *seen}) for i in range(1, len(s) + 1) if (candidate := s[:i]) not in seen), default=0)
        
        
        

        rt = helper(s, set())
        return rt


          


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        for answer in range(len(s), 0, -1):
            num_splits = answer - 1
            for split_points in combinations(range(1, len(s)), num_splits):
                current = 0
                words = set()
                for split_point in split_points:
                    words.add(s[current:split_point])
                    current = split_point
                words.add(s[current:])
                if len(words) == answer:
                    return answer

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        spl = list(s)
        n = len(spl)
        c = collections.Counter(spl)
        if all(v==1 for v in c.values()):
            return n
        mx = 2**(n-1)-2
        ans = 1
        for cmb in range(mx,0,-1):            
            bs = list(bin(cmb)[2:].zfill(n-1))
            if bs.count('1')+1<ans:
                #if cmb<2**10:
                    #print(cmb,bs)
                continue
            spl = []
            sub = s[0]
            for i,b in enumerate(bs):
                if b=='0':
                    sub += s[i+1]
                else:
                    spl.append(sub)
                    sub = s[i+1]
            spl.append(sub)
            c = collections.Counter(spl)
            if all(v==1 for v in c.values()):
                if len(spl)>ans:
                    ans = len(spl)
                    #print(n,cmb,ans,spl)
        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        val=0
        if len(s)==0:
            return val
        def helper(s, sett=()):
            return max((1 + helper(s[i:], {candidate, *sett}) for i in range(1, len(s) + 1) if (candidate := s[:i]) not in sett), default=0)
        val=helper(s)
        return val


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n = len(s)
        currli = []
        visiting = set()
        self.maxval = 1
        def dfs(st, s):
            if len(s) <= 0:
                self.maxval = max(self.maxval, len(currli))
                return True
            # if i >= n:
            #     # currli.append(s)
            #     if s not in visiting:
            #         return True
            #     else:
            #         return False
                
            for i in range(1, len(s) + 1):
                # print(s[0:i], s)
                if s[0:i] not in visiting:
                    visiting.add(s[0:i])
                    currli.append(s[0:i])
                    dfs(i, s[i:])
                    # if dfs(i, s[i:]):
                    #     return True
                    currli.pop()
                    visiting.remove(s[0:i])
                
            return False
            
            
        
        
        for i in range(1, n+1):
            visiting.add(s[0:i])
            currli.append(s[0:i])
            # print(s[0:i], s[i:])
            dfs(i, s[i:])
            # if dfs(i, s[i:]):
            #     break
            currli.pop()
            visiting.remove(s[0:i])
            
        # return len(currli)
        return self.maxval


def partition(s):
    def backtrack(index, path):
        if index == len(s):
            res.append(list(path))
        else:
            path.append(s[index])
            backtrack(index+1, path)
            path.pop()

            if path:
                path[-1] = path[-1] + s[index]
                backtrack(index+1, path)
    res = []
    backtrack(0, [])
    return res
class Solution:
    
    def maxUniqueSplit(self, s: str) -> int:
        ans = 0
        lst = partition(s)
        for prt in lst:
            if(len(set(prt)) == len(prt)):
                ans = max(ans, len(prt))
        # print(lst)
        return ans
    
    
       


class Solution:
    def maxUniqueSplit(self, s: str, seen= ()) -> int:
        return max((1 + self.maxUniqueSplit(s[i:], {candidate, *seen}) for i in range(1, len(s) + 1) if (candidate := s[:i]) not in seen), default=0)
                    
                    
            


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        res = 0
        def dfs(before_res, cur_s):
            nonlocal res
            if len(cur_s) == 0:
                res = max(res, len(before_res))
            for i in range(len(cur_s)):
                if cur_s[:i + 1] not in before_res:
                    before_res.add(cur_s[:i + 1])
                    dfs(before_res, cur_s[i + 1:])
                    before_res.remove(cur_s[:i + 1])
        
        dfs(set(), s)
        return res


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        self.res = 1
        
        def backtrack(curr, idx):
            if len(curr) != len(set(curr)):
                return
            else:
                if idx == len(s):
                    self.res = max(self.res, len(curr))
                    return
            for i in range(idx + 1, len(s) + 1):
                backtrack(curr + [s[idx : i]], i)
        
        backtrack([], 0)
        
        return self.res

import copy
class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n = len(s)
        def dfs(temp, s, res):
            if len(s) == 0:
                if len(''.join(list(set(temp)))) == n and len(temp) > len(res):
                    res = copy.deepcopy(temp)
                return res
            for i in range(1, len(s) + 1):
                
                temp.append(s[:i])
                # print(temp)
                res = dfs(temp, s[i:], res)
                temp.pop()
            return res
        
        return len(dfs([], s, []))


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        
        
        # my solution after contest ends ... 68 ms ... 80 % ... 13.6 MB ... 100 %
        #  time: O()
        # space: O()
        
        def backtrack(seen, sidx):
            if sidx == len(s):
                self.res = max(self.res, len(seen))
                return
            if len(seen) + len(s) - sidx <= self.res:  # 截断条件提速  600 ms ===> 68 ms
                return
            for eidx in range(sidx, len(s)):
                if s[sidx:eidx+1] not in seen:
                    backtrack(seen | {s[sidx:eidx+1]}, eidx+1)
        self.res = 1
        backtrack(set(), 0)
        return self.res
        
        


# class Solution:
#     def maxUniqueSplit(self, s: str) -> int:
#         def helper(s, seen):
#             return max((1 + helper(s[i:], {candidate, *seen}) for i in range(1, len(s) + 1) if (candidate := s[:i]) not in seen), default=0)

#         rt = helper(s, set())
#         return rt


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        self.res = 0
        def dfs(s, path):
            if not s: self.res = max(self.res, len(path))
            for i in range(1,len(s)+1):
                dfs(s[i:],path|{s[:i]})
        dfs(s,set())
        return self.res

          


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        def max_uni_seq(s, vis=()):
            return max((1 + max_uni_seq(s[i:], {sol, *vis}) for i in range(1, len(s) + 1) if (sol := s[:i]) not in vis), default=0)
        
        return max_uni_seq(s)

import functools
class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        @functools.lru_cache(None)
        def dp(i):
            res=[{s[:i+1]}]
            for j in range(0,i):
                for sets in dp(j):
                    if s[j+1:i+1] not in sets:
                        res.append(sets|{s[j+1:i+1]})
            return res
        return max([len(set_) for set_ in dp(len(s)-1)])

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def max_unique(s, visited=()):
            return max((1 + max_unique(s[i:], {candidate, *visited}) for i in range(1, len(s) + 1) if (candidate := s[:i]) not in visited), default=0)
        return max_unique(s)


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        ans = [0]
        def split(curr, ind):
            if ind >= len(s):
                return len(curr)
            for i in range(ind + 1, len(s) + 1):
                tmp = curr.copy()
                tmp.add(s[ind:i])
                s1 = split(tmp, i)
                ans[0] = max(ans[0], s1)
            return len(curr)
        split(set(), 0)
        return ans[0]
                


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def max_unique_substrings(s, seen=()):
            return max((1 + max_unique_substrings(s[i:], {candidate, *seen}) for i in range(1, len(s) + 1) if (candidate := s[:i]) not in seen), default=0)
        return max_unique_substrings(s)

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        from functools import lru_cache
        
        L = len(s)
        
        @lru_cache(None)
        def DP(idx, seen):
            if idx == L:
                return len(seen)
            res = 0
            for i in range(idx+1, L+1):
                temp = s[idx:i]
                if temp in seen:
                    continue
                res = max(res, DP(i, seen|{temp}))
            return res
                
            
        
        return DP(0, frozenset())
                    
        



def max_unique_substrings(s, seen=()):
    return max((1 + max_unique_substrings(s[i:], {candidate, *seen}) for i in range(1, len(s) + 1) if (candidate := s[:i]) not in seen), default=0)
class Solution:
    
    def maxUniqueSplit(self, s: str) -> int:
        return max_unique_substrings(s,());
        


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def solve(last, idx, cur):
            if idx == len(s):
                if len(cur) == len(set(cur)):
                    self.ans = max(self.ans, len(cur))
                return
            
            cur.append(s[last:idx+1])
            solve(idx+1, idx+1, cur)
            cur.pop()
            
            solve(last, idx+1, cur)
        self.ans = 0
        solve(0, 0, [])
        return self.ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
    
        res = 1
        
        def dfs(pos, path):
            nonlocal res
            
            if pos == len(s):
                res = max(res, len(set(path)))
                
            for i in range(pos + 1, len(s) + 1):
                path.append(s[pos:i])
                dfs(i, path)
                path.pop()
                
        dfs(0, [])
        return res

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        res = 0
        dfs = [[set(),s]]
        while dfs:
            curSet, curS = dfs.pop()            
            res = max(res, len(curSet))
            if len(curSet)+len(curS) <= res or len(curS) == 0:
                   continue
                      
            for i in range(len(curS)):
                if curS[:i+1] in curSet: continue
                    
                curSet.add(curS[:i+1])
                dfs.append([curSet.copy(), curS[i+1:]])
                curSet.remove(curS[:i+1])
                   
        return res
        
            
            
                
            


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        if s  == None or len(s) == 0:
            return 0
        self.res = 0
        has = set()
        def dfs(cur, lasti, ct):
            if cur > len(s):
                self.res = max(self.res, ct)
                return
            for cur in range(cur, len(s) + 1):
                if s[lasti : cur] not in has:
                    has.add(s[lasti : cur])
                    ct += 1
                    dfs(cur + 1,cur, ct)
                    ct -= 1
                    has.remove(s[lasti : cur])
                else:
                    while cur <= len(s) and s[lasti : cur] in has:
                        cur += 1
                    dfs(cur,lasti, ct)
        dfs(1,0,0)
        return self.res
                


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def divide(s):
            for i in range(1, len(s)):
                low = s[0: i]
                high = s[i: ]
                yield (low, high)
                for div in divide(high):
                    ret = [low]
                    ret.extend(div)
                    yield ret

        combinations = list(divide(s))
        combinations.append(s)
        # print(combinations)
        ret = 1
        for comb in combinations:
            if len(comb) == len(set(comb)):
                # print(comb, set(comb))
                ret = max(ret, len(comb))
        return ret


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        visited = set()
        def dfs(start):
            nonlocal visited
            if start == len(s):
                return 0
            res = 0
            for i in range(start,len(s)):
                if s[start:i+1] not in visited:
                    visited.add(s[start:i+1])
                    res = max(res, 1+ dfs(i+1))
                    visited.remove(s[start:i+1])
                else:
                    res = max(res, dfs(i+1))
            return res
        return dfs(0)

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        self.res = 0
        def dfs(s, path):
            if not s: self.res = max(self.res, len(path))
            for i in range(1,len(s)+1):
                dfs(s[i:],path|{s[:i]})
        dfs(s,set())
        return self.res

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        combin_dict = {s[0]:[set(s[0])]}
        for index, char in enumerate(s[1:]):
            new_dict = {}
            for last_str, sets in combin_dict.items():
                for combin_set in sets:
                    
                    if char not in new_dict:
                        new_dict[char] = []
                    single_new_set = combin_set | set(char)
                    if len(''.join(combin_set)) == index+1:
                        new_dict[char].append(single_new_set)
                    
                    new_last = last_str+char
                    if len(''.join(combin_set)) == index+1:
                        new_set = combin_set.difference(set([last_str]))
                    else:
                        new_set = combin_set
                    new_set.add(new_last)
                    if new_last not in new_dict:
                        new_dict[new_last] = []
                    new_dict[new_last].append(new_set)
            combin_dict = new_dict
            
            
        res = 0
        for key, value in combin_dict.items():
            for value_set in value:
                if len(''.join(value_set)) == len(s):
                    res = max(res, len(value_set))
        return res

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def f(s, seen):
            if not s: return 0
            res = 0
            for i in range(1,len(s)+1):
                chunk = s[:i]
                if chunk not in seen:
                    res = max(res, f(s[i:], seen | {chunk}) + 1)
            return res
        return f(s, set())
                


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        ans = 0
        queue = [(set([s[:i]]), s[i:]) for i in range(1, len(s) + 1)]
        while queue:
            curSet, curS = queue.pop(0)
            if curS == '':
                ans = max(ans, len(curSet))

            for i in range(1, len(curS) + 1):
                if curS[:i] in curSet:
                    continue
                else:
                    tmpSet = curSet.copy()
                    tmpSet.add(curS[:i])
                    queue.append((tmpSet, curS[i:]))

        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        res = 0
        dfs = [[set(),s]]
        while dfs:
            curEl = dfs.pop()            
            res = max(res, len(curEl[0]))
            if len(curEl[0])+len(curEl[1]) <= res or len(curEl[1]) == 0:
                   continue
                      
            for i in range(len(curEl[1])):
                if curEl[1][:i+1] in curEl[0]: continue
                    
                curEl[0].add(curEl[1][:i+1])
                dfs.append([curEl[0].copy(), curEl[1][i+1:]])
                curEl[0].remove(curEl[1][:i+1])
                   
        return res
        
            
            
                
            


class Solution:
    def helper(self, s,occur):
        if len(s) == 0:
            return 0
        curMax = -1
        for i in range(1,len(s)+1):
            if s[:i] not in occur:
                occur.append(s[:i])
                if (s[i:],tuple(occur)) in self.memo:
                    res = self.memo[(s[i:],tuple(occur))]
                else:
                    res = self.helper(s[i:], occur)
                    self.memo[(s[i:],tuple(occur))] = res
                if res >= 0:
                    curMax = max(curMax, 1+res)
                occur.pop()
        return curMax
        
    def maxUniqueSplit(self, s: str) -> int:
        self.memo = {}
        return self.helper(s,[])


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n= len(s)
        def back(i, curr, addhere ):
            if i==n:
                return len(addhere)-1
            if curr+s[i] in addhere:
                return back(i+1, curr+s[i], addhere.copy())
            else:
                return max( back(i+1, '', addhere.union({curr+s[i]})), back(i+1, curr+s[i], addhere.copy())   )
        b = set()
        b.add('')
        return back(0,'',b)
        


class Solution:
    ans=1
    def getans(self,s,start,n,temp):
        self.ans=max(self.ans,len(temp))
        for x in range(start+1,n+1):
            boss=set(list(temp))
            boss.add(s[start:x])
            self.getans(s,x,n,boss)
            
            
    def maxUniqueSplit(self, s: str) -> int:
        temp=set()
        self.getans(s,0,len(s),temp)
        return self.ans
            


import itertools
class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        positions = []
        for i in range(1,len(s)):
            positions.append(i)
        if(len(s) < 3):
            if(s[0] != s[1]):
                return 2
        maximally_split = 1
        for i in range(1,len(s)):
            separate_positions = list(itertools.combinations(positions,i))
            for separate_position in separate_positions:
                curr_position = 0
                curr_idx = 0
                substrings = []
                while(curr_idx < len(separate_position)):
                    substrings.append(s[curr_position:separate_position[curr_idx]])
                    curr_position = separate_position[curr_idx]
                    curr_idx += 1
                substrings.append(s[curr_position:])
                length_of_unique_list = len(set(substrings))
                if(length_of_unique_list == len(substrings)):
                    if(length_of_unique_list > maximally_split):
                        maximally_split = length_of_unique_list
        if(len(set(list(s))) > maximally_split):
            maximally_split = len(set(list(s)))
        return maximally_split

def max_unique_substrings(s, seen=()):
    return max((1 + max_unique_substrings(s[i:], {candidate, *seen}) for i in range(1, len(s) + 1) if (candidate := s[:i]) not in seen), default=0)


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        return max_unique_substrings(s)

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def solve(start, visited, memo):
            state = (start, tuple(visited))
            if start >= len(s):
                return 0
            if state in memo:
                return memo[state]
            result = 0
            for idx in range(start, len(s)):
                cut_str = s[start:idx + 1]
                pos = get_position(cut_str)
                if visited[pos]:
                    continue
                visited[pos] = True
                
                result = max(result, 1 + solve(idx + 1, visited, memo))
                visited[pos] = False
            memo[state] = result
            return result
        def get_position(string):
            return self.sub_str_pos[string]
        self.sub_str_pos = {}
        for i in range(len(s)):
            for j in range(i, len(s)):
                sub_str = s[i:j + 1]
                if sub_str not in self.sub_str_pos:
                    self.sub_str_pos[sub_str] = len(self.sub_str_pos)
        return solve(0, [False for _ in range(len(self.sub_str_pos))], {})


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def split(s):
            if not s:
                return [set()]
            n = len(s)

            w = set()
            w.add(tuple([s]))

            ret = [set([s])]
            if n == 1:
                return ret
            if n == 2:
                if s[0] != s[1]:
                    ret += [set([*s])]
                return ret
            for i in range(1, n):
                ls = split(s[0:i])
                rs = split(s[i:n])
                for l in ls:
                    for r in rs:
                        if len(l.intersection(r)) == 0:
                            e = tuple(sorted(list(l | r)))
                            if e not in w:
                                w.add(e)
                                ret += [l | r]
            return ret

        if not s:
            return 0
        n = len(s)
        if n < 10:
            ws = split(s)
            return max(map(len, ws))
        else:
            ans = 0

            ls = split(s[:7])
            rs = split(s[7:])
            ws = []
            w = set()
            for l in ls:
                for r in rs:
                    if len(l.intersection(r)) == 0:
                        e = tuple(sorted(list(l | r)))
                        if e not in w:
                            w.add(e)
                            ws += [l | r]
            ans = max(ans, max(map(len, ws)))

            ls = split(s[:6])
            rs = split(s[6:])
            ws = []
            w = set()
            for l in ls:
                for r in rs:
                    if len(l.intersection(r)) == 0:
                        e = tuple(sorted(list(l | r)))
                        if e not in w:
                            w.add(e)
                            ws += [l | r]
            ans = max(ans, max(map(len, ws)))

            return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        res = 0
        dfs = [[set(),s]]
        while dfs:
            curEl = dfs.pop()            
            res = max(res, len(curEl[0]))
            if len(curEl[0])+len(curEl[1]) <= res or len(curEl[1]) == 0:
                   continue
                      
            for i in range(len(curEl[1])):
                noDel = curEl[1][:i+1] in curEl[0]
                if noDel: continue
                curEl[0].add(curEl[1][:i+1])
                dfs.append([curEl[0].copy(), curEl[1][i+1:]])
                if not noDel:
                    curEl[0].remove(curEl[1][:i+1])
                   
        return res
        
            
            
                
            


import collections
import itertools
class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def check(b):
            h = {}
            w = ''
            b = list(b) + [0] # b[len(s)-1] should be zero
            for i, v in enumerate(b):
                w += s[i]
                if v == 0:
                    if w in h: return -1
                    h[w] = 1
                    w = ''
            return len(h)
        ans = 1
        for b in itertools.product([0,1], repeat=len(s)-1):
            # if b[i]==1, b[i] is concatenated to b[i+1]
            n = check(b)
            ans = max(ans, n)
        return ans

import collections
import itertools
class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def check(b):
            h = {}
            w = ''
            for i, v in enumerate(b):
                w += s[i]
                if v == 0:
                    if w in h:
                        return -1
                    else:
                        h[w] = 1
                    w = ''
            w += s[-1]
            if w != '':
                if w in h:
                    return -1
                else:
                    h[w] = 1
            #print(h)
            return len(h)
        ans = 1
        for b in itertools.product([0,1], repeat=len(s)-1):
            n = check(b)
            if n > 0:
                ans = max(ans, n)
        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        # len(s) <= 16, only lower_case
        n = len(s)
        mx = 1
        m = n - 1
        total = (1 << m)
        state = 0
        for state in range(total):
            seen = set()
            lo = 0
            for i in range(m + 1):
                if state & (1 << i):
                    token = s[lo:i + 1]
                    if token in seen:
                        break
                    else:
                        seen.add(token)
                    lo = i + 1
            else:
                token = s[lo:n]
                if token not in seen:
                    seen.add(token)
                    mx = max(len(seen), mx)
        return mx

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        i = 0
        self.res = 0
        
        
        def sub(s, x):
            if len(s) == 0:
                if sorted(x) == sorted(list(set(x))):
                    self.res = max(self.res, len(set(x)))
                return

            for i in range(1, len(s)+1):
                sub(s[i:], x + [s[:i]])
            
        res = sub(s, [])
        return self.res

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        # dp = [[\"\"] for _ in range(len(s))]
        # dp[0] = [s[0]]
        # for i in range(1, len(s)):
        #     maxnum_ = 1
        #     for j in range(i):
        #         if s[j+1:i] not in dp[j]:
        #             maxnum = len(dp[j]) + 1
        #             if maxnum > maxnum_:
        #                 maxnum_ = maxnum
        #                 dp[i] = dp[j].copy() 
        #                 dp[i].append(s[j+1:i])
        # print(dp)
        # return len(dp[len(s)-1])
#         return len(self.maxUniqueSplit_(s, len(s)-1)[-1])
    
#     @lru_cache
#     def maxUniqueSplit_(self, s, i):
#         if i == 0:
#             return [[s[i]]]
#         else:
#             max_ = 0
#             toreturn = []
#             for j in range(i):
#                 maxUniqueSplit_j = self.maxUniqueSplit_(s, j)
#                 for uniquesplit_j in maxUniqueSplit_j:
#                     if s[j+1:i+1] not in uniquesplit_j:
#                         if len(uniquesplit_j) + 1 > max_:
#                             toreturn = [uniquesplit_j + [s[j+1:i+1]]]
#                             max_ = len(uniquesplit_j) + 1
#                         elif len(uniquesplit_j) + 1 == max_:
#                             toreturn.append(uniquesplit_j + [s[j+1:i+1]])
#                     if j == i - 1 and len(toreturn) == 0:
#                         toreturn = [uniquesplit_j]
#             print(toreturn, i)
#             return toreturn
        if len(s) == 1:
            return 1
        def splitter(str):
            for i in range(1, len(str)):
                start = str[0:i]
                end = str[i:]
                yield (start, end)
                for split in splitter(end):
                    result = [start]
                    result.extend(split)
                    yield result
        
        maxnum = 0
        for split in splitter(s):
            if len(set(split)) == len(split):
                maxnum = max(len(split), maxnum)
        if maxnum == 0:
            return self.maxUniqueSplit(s[:len(s)-1])
        else:
            return maxnum
                


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        dp = [[] for i in range(len(s))]
        dp[0].append([s[0]])
        
        for i in range(1, len(s)):
            for j in range(len(dp[i-1])):
                comb = dp[i-1][j]
                
                dp[i].append(comb[:-1]+[comb[-1]+s[i]])
                dp[i].append(comb+[s[i]])
        _max = 0
        
        for i in range(len(s)):
            for j in range(len(dp[i])):
                length = len(set(dp[i][j]))
                if length >_max:
                    _max = length
                
        return _max
            


from collections import defaultdict
class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n = len(s)
        memo = [[] for _ in range(n)]
        def unique_split(i):
            if memo[i]:
                return memo[i]
            memo[i].append(set([s[:i+1]]))
            for j in range(i):
                sets = unique_split(j)
                for sub in sets:
                    if s[j+1:i+1] not in sub:
                        memo[i].append(sub|set([s[j+1:i+1]]))
            return memo[i]
        sublen = [len(lst) for lst in unique_split(n-1)]
        # print(memo)
        return max(sublen)


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        from itertools import combinations
        for k in reversed(list(range(len(s) + 1))):
            for comb in combinations(list(range(1, len(s))), k):
                split_idxs = [0, *comb, len(s)]
                splits = []
                for prev, next in zip(split_idxs, split_idxs[1:]):
                    splits.append(s[prev:next])
                if len(set(splits)) == len(splits):
                    return len(splits)
        return 0



import itertools
class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        maxres = 1
        for sep in itertools.product([0,1], repeat = len(s)-1):
            # print(sep)
            sett = set()
            cur = s[0]
            for i,(se,c) in enumerate(zip(sep, s[1:]), start=1):
                if se:
                    if cur in sett:
                        break
                    sett.add(cur)
                    cur = c
                else:
                    cur += c
            else:
                if cur in sett:
                    continue
                sett.add(cur)
                # print(sep, sett)
                maxres = max(maxres, len(sett))
        return maxres
        


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        # take greedy 
        words = list(s)
        N = len(words)
        ans = 0
        def backtrack(words, s):
            nonlocal ans
            n = len(words)
            if n==0:
                ans = max(len(s), ans)
            for i in range(1, n+1):
                if str(words[:i]) not in s:
                    s.add(str(words[:i]))
                    backtrack(words[i:], s)
                    s.remove(str(words[:i]))
                    
        backtrack(words, set())
        return ans


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        # print(s)
        le = len(s) - 1
        max = 1
        for ma in range(pow(2, le) - 1, 0, -1):
            bi = format(ma, '0' + str(le) + 'b') + '1'
            prev = 0
            lis = []
            valid = True
            for bit in range(len(bi)):
                if bi[bit] == '1':
                    part = s[prev:bit + 1]
                    if part in lis:
                        valid = False
                        break
                    lis.append(part)
                    prev = bit + 1
            if valid and len(lis) > max:
                max = len(lis)
        return max
                


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        if len(s) == 1:
            return 1
        
        n = len(s)
        # dic = {}
        # def helper(length,s,res):
        #     if idx == n:
        #         return
        #     s = s[:]
            
                
        
        dp = [0] * (n+1)
        dp[0] = [set()]
        
        for end in range(1,n+1):
            ls = []
            sub = set()
            for start in range(end):
                for ele in dp[start]:
                    last = ele.copy()
                    node = s[start:end]
                    last.add(node)
                    ls.append(last)
                        #sub = last
            dp[end] = ls
        res = 0
        for i in dp[-1]:
            if len(i) > res:
                res = len(i)
        return res
                
                


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        to_ret = 0
        for bin_i in range(2**(len(s)-1)) :
            to_deal = set()
            mark=True
            last = s[0]
            for i in range(len(s)-1) :
                cn = s[i+1]
                if (bin_i & (1<<i))  :
                    if last in to_deal :
                        mark = False
                        break
                    to_deal.add(last)
                    last = cn
                else :
                    last += cn
            if last in to_deal :
                mark = False
            else :
                to_deal.add(last)
            if mark : 
                to_ret = max(to_ret, len(to_deal))
        return to_ret

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n = len(s)
        ans = 0
        for pat in range(1 << n-1):
            start = 0
            end = 1
            split = []
            # add s[start: end]
            for b in bin(pat)[2:].zfill(n - 1):
                if b == '1':
                    split.append(s[start:end])
                    start = end
                    end += 1
                else:
                    end += 1
            split.append(s[start:end])
            if len(set(split)) == len(split):
                ans = max(ans, len(split))
        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        res=[[s[0]]]

        for i in s[1:]:
            
            for _ in range(len(res)):
                j=res.pop(0)
                res.append(j+[i])
                res.append(j[:-1]+[j[-1]+i])
 


        return max(list(map(len,list(map(set,res)))))


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        to_ret = 0
        for bin_i in range(2**(len(s)-1)) :
            to_deal = set()
            mark=True
            last = s[0]
            for i in range(len(s)-1) :
                cn = s[i+1]
                if (bin_i & (1<<i)) > 0 :
                    if last in to_deal :
                        mark = False
                        break
                    to_deal.add(last)
                    last = cn
                else :
                    last += cn
            if last in to_deal :
                mark = False
            else :
                to_deal.add(last)
            if mark : 
                to_ret = max(to_ret, len(to_deal))
        return to_ret

from itertools import combinations

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        # Loop over possible number of splits
        for num_splits in reversed(range(1, len(s))):
            num_strings = num_splits + 1
            # Split the string at those starting indices
            for split_indices in combinations(range(1, len(s)), num_splits):
                indices = [0] + list(split_indices) + [len(s)]
                
                split_strs = set()
                for start, end in zip(indices[:-1], indices[1:]):
                    split_strs.add(s[start:end])
                if len(split_strs) == num_strings:
                    return num_strings  # We did it!
        
        # We couldn't find a splitting
        return 1

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        d = {}
        for i in s:
            if i in d:
                d[i] += 1
            else:
                d[i] = 1
        if len(d) == len(s):
            return len(d)
        
        def waysToSplit(s): # return list of sequences
            if not s:
                return []
            if len(s) == 1:
                return [[s]]
            else:
                res = []
                for i in range(len(s)):
                    first = [s[:i+1]]
                    second = waysToSplit(s[i+1:])
                    for seq in second:
                        res.append(first + seq)
                res.append([s])
            return res
        
        maxCount = 1
        
        sequences = waysToSplit(s)
        #print(sequences)
        for seq in sequences:
            s = set()
            count = 0
            foundDup = False
            for element in seq:
                if element in s:
                    foundDup = True
                    break
                else:
                    count += 1
                    s.add(element)
            if not foundDup:
                maxCount = max(maxCount, count)
        return maxCount
                
                


from functools import lru_cache
class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        @lru_cache(None)
        def rec(i, fs):
            if i == len(s):
                return 0
            ans = float('-inf')
            sub = ''
            for j in range(i, len(s)):
                sub += s[j]
                if sub not in fs:
                    ans = max(ans, rec(j+1, fs | frozenset([sub])) + 1)
            return ans
        return rec(0, frozenset())

class Solution:
    def f(self, s):    
        xss = []
        if len(s) == 0:
            temp = []
            temp.append('')
            xss.append(temp)
            return xss
        for i in range(1,len(s)+1):
            xs = self.f(s[i:])
            for x in xs:
                if s[:i] not in x:
                    x.append(s[:i])
                    xss.append(x)
  
        return xss
                
    def maxUniqueSplit(self, s: str) -> int:
        x = max([len(y) for y in self.f(s)])
        
        return x-1

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def permutations(s):
            result = [[s]]
            for i in range(1,len(s)):
                start = [s[:i]]
                end = s[i:]
                for p in permutations(end):
                    result.append(start + p)
            return result
        
        l = permutations(s)
        #print(l)
        maxt = 0
        totalset = set()
        for i in l:
            if len(set(i)) == len(i):
                if len(i) > maxt:
                    maxt = len(i)                 
        return maxt

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n = len(s)
        res = 1
        if n == 1: return res
        for x in range(2**(n-1)):
            m = 1<<(n-2)
            p0 = 0
            p1 = 0
            st = set()
            done = False
            while m:
                if x&m:
                    sr = s[p0:p1+1]
                    if sr in st:
                        done = True
                        break
                    st.add(sr)
                    p0 = p1 + 1
                    p1 = p1 + 1
                else:
                    p1 += 1
                m>>=1
            if not done:
                sr = s[p0:p1 + 1]
                if sr not in st: res = max(res, len(st) + 1)
        return res

from functools import lru_cache
class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        @lru_cache(None)
        def helper(s, n):
            # print(s, n)
            ts = set()
            cs = ''
            for i in range(len(s)):
                cs += s[i]
                if n % 2 == 1:
                    if cs in ts:
                        # print(ts, cs)
                        return -1
                    else:
                        ts.add(cs)
                        cs = ''
                    n = n//2
                else:
                    n = n//2
                    continue
            if cs != '':
                if cs in ts:
                    # print(ts, cs)
                    return -1
                else:
                    ts.add(cs)
            # print(ts)
            return len(ts)
        
        r = -1
        for i in range(0, 2**(len(s)-1)):
            r = max(r, helper(s, i))
        return r
                    
        


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n=len(s)
        if n==1:
            return 1
        from itertools import combinations
        L=list(range(1,n))
        for d in range(n-1,0,-1):
            for x in combinations(L,d):
                hh=[0]+list(x)+[n]
                tmep=[s[hh[j]:hh[j+1]] for j in range(len(hh)-1)]
                if len(set(tmep))==len(tmep):
                    return d+1
        return 1
                


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n = len(s)
        ans = 1
        for i in range(2 ** (n-1)):
            b = '1' + bin(i)[2:].zfill(n-1) + '1'
            pr = 0
            w = set()
            flag = True
            for k in range(1, n+1):
                if k == n or b[k] == '1':
                    chrs = s[pr: k]
                    if chrs in w:
                        flag = False
                        break
                    w.add(chrs)
                    pr = k
            if flag:
                ans = max(ans, len(w))
        return ans
        
            
            
        
        
        
#         @lru_cache(None)
#         def dp(s):
#             if s == '':
#                 return set()
#             if len(s) == 1:
#                 return set([s[0]])
#             ans = 0
#             com = set()
#             for i in range(1,len(s)+1):
#                 l = set([s[:i]])
#                 r = dp(s[i:])
#                 if i != len(s) and len(r) == 0: # unvalid right
#                     continue
                
#                 if len(l.intersection(r)) == 0:
#                     if len(l) + len(r) > ans:
#                         ans = len(l) + len(r)
#                         com = l.union(r)
#             return com
        
#         print(dp(s))
#         return len(dp(s))
                    
            
            


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def split(s):
            if len(s) == 0:
                return []
            if len(s) == 1:
                return [[s]]
            res = []
            for i in range(1,len(s) + 1):
                ans = [s[:i]]
                splits = split(s[i:])
                if splits:
                    for sub in splits:
                        res.append(ans + sub)
                else:
                    res.append(ans)
            return res
        
            
        options = split(s)
        m = 0
        for o in options:
            if len(o) == len(set(o)):
                m = max(m, len(o))
        return m

class Solution:
    def dfs(self, s, req_l, segs, cur, hs):
        if cur >= len(s):
            return segs == req_l

        for pos in range(cur, len(s)):
            ts = s[cur:pos+1]
            if ts in hs:
                continue
            hs.add(ts)
            if self.dfs(s, req_l, segs+1, pos+1, hs):
                return True
            hs.remove(ts)
        return False

    def maxUniqueSplit(self, s: str) -> int:
        for i in range(len(s), 0, -1):
            if self.dfs(s, i, 0, 0, set()):
                return i
        return 1


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def check(s):
            if len(s)==1:
                return [[s]]
            if len(s)==0:
                return[[]]
            ans = []
            for i in range(1,len(s)+1):
                for item in check(s[i:]):
                    ans.append([s[:i]]+item)
            return ans
        result = check(s)
        ans = 0
        for item in result:
            if len(set(item)) == len(item):
                ans = max(len(item),ans)
        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        ans = 0
        for i in range(1, 2**(len(s) - 1) + 1):    
            prev = 0
            seen = set()
            for j in range(0, len(s)):
                if i & (1 << j):
                    seen.add(s[prev:(j+1)])
                    prev = j + 1
            final = s[prev:len(s)]
            if len(final):
                seen.add(final)
            ans = max(ans, len(seen))
        return ans

class Solution:
    def maxUniqueSplit(self, ss: str) -> int:
        @lru_cache(None)
        def dfs(s, words):
            if not s: return 0
            res = 0
            words = set(words)
            for i in range(len(s)):
                if s[:i+1] not in words:
                    res = max(res, 1 + dfs(s[i+1:], tuple(words | set([s[:i+1]]))))
            return res
        return dfs(ss, ())


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n=len(s)
        ans=-1
        for bit in range(1<<n-1):
            sep=[]
            for i in range(n-1):
                if bit>>i&1:sep.append(i+1)
            sep.append(n)
            ww=set()
            l=r=0
            ng=False
            for r in sep:
                w=s[l:r]
                if w in ww:
                    ng=True
                    break
                ww.add(w)
                l=r
            if ng:continue
            ans=max(ans,len(ww))
        return ans


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def split(s):
            if not s:
                return [set()]
            n = len(s)

            w = set()
            w.add(tuple([s]))

            ret = [set([s])]
            if n == 1:
                return ret
            if n == 2:
                if s[0] != s[1]:
                    ret += [set([*s])]
                return ret
            for i in range(1, n):
                ls = split(s[0:i])
                rs = split(s[i:n])
                for l in ls:
                    for r in rs:
                        if len(l.intersection(r)) == 0:
                            e = tuple(sorted(list(l | r)))
                            if e not in w:
                                w.add(e)
                                ret += [l | r]
            return ret

        if not s:
            return 0
        n = len(s)
        if n < 12:
            ws = split(s)
            return max(map(len, ws))
        else:
            ans = 0

            ls = split(s[:8])
            rs = split(s[8:])
            ws = []
            w = set()
            for l in ls:
                for r in rs:
                    if len(l.intersection(r)) == 0:
                        e = tuple(sorted(list(l | r)))
                        if e not in w:
                            w.add(e)
                            ws += [l | r]
            ans = max(ans, max(map(len, ws)))

            return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def split(s, b): #split into substrings given bit string b
            res = []
            x, y = s[0], b[0]
            for i in range(1, len(s)):
                if b[i]==y:
                    x += s[i]
                else:
                    res.append(x)
                    x, y = s[i], b[i]
            res.append(x)
            return res
                    
        count = 0
        for i in range(2**(len(s)-1)):
            b = bin(i)[2:]
            bb = '0' * (len(s) - len(b)) + b    # padding + bits
            res = split(s, bb)
            #print(bb, res)
            if len(res) == len(set(res)):
                count = max(count, len(res))
                
        return count


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        l = len(s)
        for i in range(l - 1, 0, -1):
            for j in itertools.combinations(range(1, l), i):
                cut = [0] + list(j)
                subs = []
                for k in range(len(cut)):
                    if k == len(cut) - 1:
                        subs.append(s[cut[k]:])
                    else:
                        subs.append(s[cut[k]: cut[k + 1]])
                if len(subs) == len(set(subs)):
                    return len(subs)
        return 1

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def split(s, b): #split into substrings given bit string b
            res = []
            x, y = s[0], b[0]
            for i in range(1, len(s)):
                if b[i]==y:
                    x += s[i]
                else:
                    res.append(x)
                    x, y = s[i], b[i]
            res.append(x)
            return res
        
        max_len = 0
        for i in range(2**(len(s)-1)):
            b = bin(i)[2:]
            b = '0'*(len(s)-len(b)) + b
            res = split(s,b) #split based on bit string
            if len(res)==len(set(res)): #check if the split forms valid substrings
                max_len = max(max_len, len(res)) #compare against max length so far
        return max_len


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        res = 0
        for count in range(len(s)):
            for partitions in combinations(range(1, len(s)), count):
                partitions = [0] + list(partitions) + [len(s)]
                parts = [s[a:b] for a, b in zip(partitions, partitions[1:])]
                if len(parts) == len(set(parts)):
                    res = max(res, len(parts))
        return res

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        result = 1
        for l in itertools.product([True, False], repeat=len(s)):
            if l[-1] == False:
                continue
            cache = list()
            now = ''
            for c, end in zip(s, l):
                now += c
                if end:
                    cache.append(now)
                    now = ''
            if len(cache) == len(set(cache)):
                result = max(result, len(cache))
        return result
        # length = len(s)
        # cache = set()
        # now = 0
        # l = 1
        # while now + l <= length:
        #     if s[now: now + l] in cache:
        #         l += 1
        #     else:
        #         cache.add(s[now: now + l])
        #         now += l
        #         l = 1
        # return len(cache)


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n = len(s)-1
        ans = 1
        for i in range(2**n+1):
            prev = 0
            ok = True
            visited = set()
            for j in range(n):
                if i & (1<<j):
                    tmp = s[prev:j+1]
                    prev = j+1
                    if tmp in visited:
                        ok = False
                        break
                    visited.add(tmp)
                    #print(visited)
                if not ok:
                    break
            if not ok:
                continue
            tmp = s[prev:]
            #print(tmp, visited)
            if tmp not in visited:
                #print(visited)
                ans = max(ans, len(visited) + 1)
        return ans            
                    
        


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def allsplit(s):
            if len(s)==1:
                return [[s]]
            
            res = [[s]]
            for i in range(1,len(s)):
                res += [[s[:i]] + x for x in allsplit(s[i:])]
            return res
        
        ans = 0
        
        for sp in allsplit(s):
            # print(sp)
            if len(sp) == len(set(sp)):
                ans = max(ans, len(sp))
        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        max_length = 1

        for code in range(2 ** (len(s) - 1)):
            subs = set()

            cur = s[0]

            for i in range(1, len(s)):
                if code % 2 == 1:
                    if cur in subs:
                        break
                    subs.add(cur)
                    cur = s[i]
                else:
                    cur += s[i]
                code = code >> 1
            if cur not in subs:
                max_length = max(max_length, len(subs) + 1)
        return max_length

def count1(x):
    xx = x
    ans = 0
    while x != 0:
        x &= x - 1
        ans += 1
    return ans

def ok(mask, s):
    strs = []
    prev = 0
    for i in range(len(s) - 1):
        if (1 << i) & mask:
            strs.append(s[prev: i+1])
            prev = i + 1
    strs.append(s[prev:])
    # print(strs)
    return len(set(strs)) == len(strs)

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n = len(s)
        ans = 0
        for i in range(1, 1 << (n-1)):
            if ok(i, s):
                ans = max(count1(i), ans)
        return ans + 1

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n = len(s)-1
        ans = 1
        for i in range(1 << n):
            subs = set()
            start = 0
            flag = False
            for j in range(n):
                if 1 << j & i:
                    tmp = s[start:j+1]
                    if tmp in subs:
                        flag = True
                        break
                    subs.add(tmp)
                    start = j+1
            if flag:
                continue
            tmp = s[start:]
            if tmp in subs:
                continue
            # print(subs, i)
            ans = max(ans, len(subs)+1)
        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        ## splitting procedure must be recursive
        # \"addbsd\" a(dd)(b)(s)(d) vs (a)(d)(db)(sd)
        # in general we want unique chars to be alone...but (adbdsd), can't always be satisfied
        # 
        N = len(s);
        
        possibilities = []

        for k in range(1, N):

            comb = itertools.combinations(list(range(1,N)), k)

            possibilities+= [[s[0:x[0]]] + [s[x[i]:x[i+1]] for i in range(len(x)-1)] + [s[x[-1]:]] for x in comb]
        ansr = 1;
        for k in possibilities:
            if(len(k) == len(set(k))):
                ansr = max(ansr, len(k));
        return ansr;
    


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def split(s, b): #split into substrings given bit string b
            res = []
            x, y = s[0], b[0]
            for i in range(1, len(s)):
                if b[i]==y:
                    x += s[i]
                else:
                    res.append(x)
                    x, y = s[i], b[i]
            
            res.append(x)
            #print(res)
            return res
        
        max_len = 0
        for i in range(2**(len(s)-1)):
            b = bin(i)[2:]
            b = '0'*(len(s)-len(b)) + b
            res = split(s,b) #split based on bit string
            if len(res)==len(set(res)): #check if the split forms valid substrings
                max_len = max(max_len, len(res)) #compare against max length so far
        return max_len

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        from collections import defaultdict
        self.ans=1
        def get(s,l,n):
            # print(l,n,len(s))
            if n==len(s):
                dic=defaultdict(int)
                for i in l:
                    dic[i]+=1
                z=True
                for i in dic:
                    if dic[i]>1:
                        z=False
                        break
                if z:
                    self.ans=max(self.ans,len(l))
                return
            i=n
            cur=''
            # print(\"here\")
            for j in range(i,len(s)):
                # print(j)
                cur+=s[j]
                # print(cur)
                get(s,l+[cur],j+1)
            
        get(s,[],0)
        return self.ans
                
                
        
        # dic=defaultdict(int)
        # n=len(s)
        # i=0
        # ans=[]
        # while i<n:
        #     cur=''
        #     j=i
        #     z=True
        #     while j<n:
        #         cur+=s[j]
        #         if dic[cur]==0:
        #             ans.append(cur)
        #             z=False
        #             dic[cur]=1
        #             j+=1
        #             break
        #         else:
        #             j+=1
        #     i=j
        #     if z:
        #         ans[-1]=ans[-1]+cur
        # return len(ans)


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        to_ret = 0
        for bin_i in range(2**(len(s)-1)) :
            to_deal = []
            last = s[0]
            for i in range(len(s)-1) :
                cn = s[i+1]
                # print(bin_i, i, (bin_i | (1<<i)))
                if (bin_i & (1<<i)) > 0 :
                    to_deal.append(last)
                    last = cn
                else :
                    last += cn
            if not last == '' :
                to_deal.append(last)
            if len(to_deal) == len(set(to_deal)) :
                to_ret = max(to_ret, len(to_deal))
        return to_ret

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def split(i):
            if i >= len(s):
                return len([v for v in t.values() if v])
            best = 0
            for j in range(i, len(s)):
                ss = s[i:j+1]
                t[ss] += 1
                best = max(best, split(j+1))
                t[ss] -= 1
            return best
                
        t = collections.defaultdict(int)
        return split(0)

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        visited = set()
        #@lru_cache(None)
        def solve(cur: str) -> int:
            ans = 0
            if not cur:
                return 0
            for i in range(1, len(s) + 1):
                candidate = cur[:i]
                if candidate not in visited:
                    visited.add(candidate)
                    ans = max(ans, 1 + solve(cur[i:]))
                    visited.remove(candidate)
            return ans
        return solve(s)
                    
        


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        visited = set()
        def solve(cur: str) -> int:
            ans = 0
            if not cur:
                return 0
            for i in range(1, len(s) + 1):
                candidate = cur[:i]
                if candidate not in visited:
                    visited.add(candidate)
                    ans = max(ans, 1 + solve(cur[i:]))
                    visited.remove(candidate)
            return ans
        return solve(s)
                    
        


#Bit Mask: use bit 1 as fence. chars between two bit 1's form a substring
#Possible choices: 2 ** N (0 ~ 2 **N - 1)
#Note: that last bit/fence does not matter so we can save computations by half
class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        N, res = len(s), 0
        
        for i in range(2 ** (N - 1)):
            start, seen = 0, set()
            for j in range(N):
                #test to see if j-th bit is 1
                if (i + (1 << N - 1)) & (1 << j):
                    seen.add(s[start : j + 1])
                    start = j + 1
            
            res = max(res, len(seen))
        
        return res
                
        
        


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        N = len(s) - 1
        res = 1
        for m in range(1 << N):
            I = [i for i in range(N) if (m >> i) & 1] + [N]
            K = len(I)
            ss = {s[:I[0]+1]}
            for k in range(K - 1):
                ss.add(s[I[k]+1: I[k+1]+1])
            # print(ss)
            if len(ss) == K:
                res = max(res, K)
        return res
            


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def all_partitions(string):
            for cutpoints in range(1 << (len(string)-1)):
                result = []
                lastcut = 0
                for i in range(len(string)-1):
                    if (1<<i) & cutpoints != 0:
                        result.append(string[lastcut:(i+1)])
                        lastcut = i+1
                result.append(string[lastcut:])
                yield result
        # d = {}
        ps = all_partitions(s)
        
        # for p in ps:
        #     print(p)
        ret = 0
        for p in ps:
            l = list(dict.fromkeys(p))
            if (len(p) == len(l)):
                ret = max(ret, len(p))
                # print(\"OK\")
                # print(p)
                # print(l)
                # print()
            #else:
                # print(\"NG\")
                # print(p)
                # print(l)
                # print()
        return ret
#         sps = []
#         for p in ps:
#             sps.append(sorted(p))
#         for p in sps:
#             print(p)
#         for p in ps:
#             d[p.sort()] = 0
#         for p in ps:
#             d[p.sort()] += 1
        
#         ret = 0
#         for p in ps:
#             if d[p.sort()] == 1:
#                 ret += 1
#         return ret


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def dfs(s, n):
            if n < 0:
                return [[s]]
            else:
                res = []
                for i in range(1, len(s) - n):
                    for group in dfs(s[i:], n - 1):
                        res.append([s[:i]] + group)
                return res
            
        res = 1
        for i in range(len(s)):
            for group in dfs(s, i):
                res = max(res, len(set(group)))         
        return res

class Solution:
    def maxUniqueSplit(self, S: str) -> int:
        n = len(S)
        ans = 0
        for U in range(1 << (n - 1)):
            word = []
            now = S[0]
            for j in range(n - 1):
                if U >> j & 1:
                    word.append(now)
                    now = S[j + 1]
                else:
                    now += S[j + 1]
            word.append(now)
            
            
            if len(word) == len(set(word)):
                ans = max(ans, len(word))
        
        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        N = len(s)
        
        res = 0
        for mask in itertools.product('10', repeat=N-1):
            mask = list(mask) + ['1']
            substr = set()
            begin = 0
            i = 0
            valid = True
            # print('mask', mask)
            while True:
                try:
                    idx = mask.index('1', begin)
                    # print('idx', idx, i, s[i:idx+1])
                    begin = idx+1
                    if s[i:idx+1] in substr:
                        valid = False
                        break
                    substr.add(s[i:idx+1])
                    i = idx+1
                except ValueError:
                    break
            if valid:
                res = max(res, mask.count('1'))
            # print('substr', substr, valid)
        return res

def get_sequences(symbols, length):
    if length == 0:
        return [[]]
    
    sequences = []
   
    tail_sequences = get_sequences(symbols, length-1)
    
    for tail_sequence in tail_sequences:
        for symbol in symbols:
            sequences.append(list(tail_sequence)+[symbol])
    
    return sequences
            

def is_unique(sequence, s):
    if s=='':
        return 0
    
    words = set()
    letters = [s[0]]
    for i in range(len(sequence)):
        if sequence[i] == 1:
            word = ''.join(letters)
            if word in words:
                return False
            words.add(word)
            letters = [s[i+1]]
        else:
            letters.append(s[i+1])
    
    word = ''.join(letters)
    if word in words:
        return False
    
    return True
class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        sequences = get_sequences([0,1], len(s)-1)
        
        max_split = 1
        for sequence in sequences:
            if is_unique(sequence, s):
                max_split = max(max_split, sum(sequence)+1)
                
        return max_split
                


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        if len(s) == 1:
            return 1
        
        if len(s) == 2:
            if s[0] == s[1]:
                return 1
            return 2
        
        ans = 0
        
        for i in range(2 ** (len(s) - 1)):
            ss = format(i, '0' + str(len(s) - 1) + 'b') + '1'
            #print(ss)
            st = set()
            count = 0
            prev = 0
            
            for j in range(len(ss)):
                lth = len(st)
                
                if ss[j] == '1':
                    st.add(s[prev:j + 1])
                    
                    if len(st) == lth:
                        break
                        
                    prev = j + 1
                    count += 1
                    
            #print(st)
            ans = max(ans, count)
            
        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        ls=len(s)
        sl=ls-1
        ps=1<<(sl)
        ans=0
        for i in range(ps):
            bi=bin(i)[2:].zfill(sl) #0 is a stick
            si=[0]+[j+1 for j in range(sl) if bi[j]=='0']+[sl+1]
            lsi=len(si)
            ds=set([s[si[j]:si[j+1]] for j in range(lsi-1)])
            if len(ds)==lsi-1:
                ans=max(ans,lsi-1)
        return ans


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        options = []
        options = self.recursiveSplit(s)
        bestcount = 0
        for option in options:
            count = 0
            encountered = {}
            valid = True
            for substr in option:
                if substr not in encountered:
                    encountered[substr] = 1
                    count += 1
                else:
                    valid = False
                    break
            if valid and count > bestcount:
                bestcount = count
        return bestcount
            
            
    def recursiveSplit(self, s:str) -> str:
        if len(s) == 1:
            return [[s]]
        elif len(s) == 0:
            return [[]]
        options = []
        for i in range(0, len(s)):
            recursiveOptions = self.recursiveSplit(s[:i])
            for option in recursiveOptions:
                newoption = option.copy()
                newoption.append(s[i:])
                options.append(newoption)
        return options



class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        c=collections.Counter(s)
        #print(c,c.keys(),len(c.keys()))
        res=len(c.keys())
        l=len(s)
        ways=int(math.pow(2,l-1))
        for i in range(ways):
            bit=str(bin(i))[2:].zfill(l-1)
            #print(bit)
            cand=[s[0]]
            for i,x in enumerate(bit):
                if x=='0':
                    cand[-1]+=s[i+1]
                else:
                    cand.append(s[i+1])
            #cand[-1]+=s[-1]
            #print(cand)
            nodup=set(cand)
            if len(nodup)==len(cand):
                res=max(res,len(cand))
        return res

from collections import Counter

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n = len(s)
        ans = 0
        
        def check(C):
            for char in list(C.keys()):
                if C[char] > 1:
                    return False
            return True
        
        curr = []
        def dfs(i):
            nonlocal ans
            if i == n:
                C = Counter(curr)
                if (check(C)):
                    ans = max(ans, len(list(C.keys())))
                return
            for j in range(i, n):
                curr.append(s[i:j+1])
                dfs(j+1)
                curr.pop()
        dfs(0)
        return ans
        


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        seen = set()
        
        def helper(start):
            nonlocal seen, s
            length = len(s)
            if start == length:
                return 0
            
            max_split, cur_split = 0, 0
            for split in range(start+1, length):
                left, right = s[start:split], s[split:length] 
                if left in seen or right in seen or left == right:
                    continue
                seen.add(left)
                cur_split = 1 + helper(split)
                seen.remove(left)
                max_split = max(max_split, cur_split)
                
            return max_split
                
        return 1 + helper(0)

#Brute Force
class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        N = len(s)
        res = 0
        
        def findSplit(num):
            bin_str = (bin(num)[2:] + '0').zfill(N)
            words = []
            word = []
            
            for c, binary in zip(s, bin_str):
                word.append(c)
                if binary == '1':
                    words.append(''.join(word))
                    word = []

            if word: words.append(''.join(word))
            #print(num, words)
            return len(set(words))
            
        
        ways = 2 ** (N - 1)
        for i in range(ways):
            res = max(res, findSplit(i))
            
        return res
            


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        res = 1
        upper = 2 ** (len(s) - 1) # so many possible breaks
        
        for i in range(upper):
            words = []
            prev = 0
            for pos in range(len(s) - 1):
                t = pos + 1
                if 1 << pos & i:
                    words.append(s[prev:t])
                    prev = t
            words.append(s[prev:])
            if len(words) == len(set(words)):
                #print(words)
                res = max(res, len(words))
        return res
            


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        def search(s):
            ans = [[s]]
            
            for i in range(1, len(s)):
                ans += [[s[:i]] + comb for comb in search(s[i:])]
                
            return ans
            
        a = search(s)
        r = 1
        for comb in a:
            # print(comb)
            if len(set(comb)) == len(comb):
                
                r = max(r, len(comb))
        
        return r

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        r=0
        m=len(s)
        for i in range(2**(m-1)):
            #b='{0:07b}'.format(i)
            bb='{0:0'+str(m-1)+'b}'
            b=bb.format(i)
            #print(b)
            st=0
            l=[]
            for k in range(len(b)):
                if b[k]=='1':
                    #print(st,k+1)
                    if k+1>st:
                        l.append(s[st:k+1])
                    st=k+1
            
            if st<len(b)+1:
                l.append(s[st:len(b)+1])
            #print(l)
            if len(l)==len(set(l)):
                r=max(r,len(l))
        print(r)
        return r

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        best = -1
        ans = []
        for i in range(2**(len(s)-1)):
            x = bin(i)
            x = x[2:]
            x = (len(s) - len(x) - 1) * '0' + x
            tmp = ''
            a = []
            c = 0
            for char in s:
                tmp += char
                if c<len(x):
                    if x[c]=='1':
                        a.append(tmp)
                        tmp = '' 
                        
                c+=1
                        
            a.append(tmp)
            
            if len(a)==len(set(a)):
                if len(a)>best:
                    best = len(a)
                    ans = a
                    
        return len(ans)


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        res = 0
        dfs = [[set(),s]]
        while dfs:
            #print(dfs)
            curEl = dfs.pop()            
            res = max(res, len(curEl[0]))
            if len(curEl[0])+len(curEl[1]) <= res or len(curEl[1]) == 0:
                   continue
                      
            for i in range(len(curEl[1])):
                noDel = curEl[1][:i+1] in curEl[0]
                curEl[0].add(curEl[1][:i+1])
                dfs.append([curEl[0].copy(), curEl[1][i+1:]])
                #print([curEl[0].copy(), curEl[1][i+1:]])
                if not noDel:
                    curEl[0].remove(curEl[1][:i+1])
                   
        return res
        
            
            
                
            


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        # dfs O(2^n) / O(n)
        def dfs(index, visited):
            nonlocal ans
            
            # if we have not seen the rest, then our answer is at least 1 larger
            if s[index:n] and s[index:n] not in visited:
                ans = max(ans, len(visited) + 1)
            
            #try each section of the remaining
            for i in range(index, n):
                # only if it doesn't exist yet, and it is not impossible to beat current max
                if s[index:i] and s[index:i] not in visited and len(visited) + 1 + n - i > ans: # prune
                    visited.add(s[index:i])
                    dfs(i, visited)
                    visited.remove(s[index:i])

        n, ans = len(s), 0
        dfs(0, set())
        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n=len(s)
        if n==1:
            return 1
        res=1
        seen=set()
        for m in range(1,1<<(n-1)):  #尝试所有切割位置
            if bin(m).count('1')<res:
                continue
            valid=True
            p=0
            for i in range(1,n+1):
                if valid:
                    if m & (1 << (i - 1)) or i == n:
                        if s[p:i] in seen:
                            valid=False
                        seen.add(s[p:i])
                        p=i
            if valid:
                res=max(res,len(seen))
            seen=set()
        return res

class Solution:
    #1593
    def maxUniqueSplit(self, s: str) -> int:
        def helper(s1_set, s2):
            N = len(s2)
            if N == 1:
                if s2 in s1_set:
                    return 0
                return len(s1_set)+1
            res = 0 if s2 in s1_set else len(s1_set)+1
            for i in range(1, N):
                if s2[:i] in s1_set:
                    continue
                s1_set.add(s2[:i])
                res = max(res, helper(s1_set,s2[i:]))
                s1_set.discard(s2[:i])
            return res
        res = helper(set(), s)
        return res

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        def helper(s, strings=set()):
            
            leng_s = len(s)
            leng_set = len(strings)
            if leng_s == 1 and s in strings:
                return 0
            else:
                ans = leng_set + 1
                for i in range(1, leng_s):
                    substr = s[:i]
                    if substr not in strings:
                        ans = max(ans, helper(s[i:], strings|{substr}))
                return ans               
                    
        return helper(s)
        
        #    if len(s) == 1 and s in soFar:
        #         return 0
        #     maxSplit = len(soFar)+1
        #     for partition in range(1, len(s)):
        #         a = s[:partition]
        #         b = s[partition:]
        #         if a not in soFar:
        #             maxSplit = max(maxSplit, maxU(b, soFar|{a}))
        #     return maxSplit
        # return maxU(s)


from functools import lru_cache

def _helper(s: str, visited) -> int:
    # s: remaining string to be split
    # count: number of unique pieces already
    # visited: set of string that already be used
    # Returns: the maximum number of unique
    # string pieces we can get
    
    # Iterate the first split point.
    n = len(s)
    result = 0
    for i in range(n - 1):
        # Cut after i-th char.
        cut, remain = s[:(i + 1)], s[(i + 1):]
        if cut in visited:
            continue
        visited.add(cut)
        result = max(result, 1 + _helper(remain, visited))
        visited.remove(cut)
    
    # Another option is no cutting
    if not s in visited:
        result = max(result, 1)
    return result
    

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        # DFS/Backtracking,
        # Consider caching to reduce the change of TLE
        
        if not s:
            return 0
        
        visited = set()
        return _helper(s, visited)
        
    
    
        


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def maxU(s, soFar=set()):
            if len(s) == 1:
                if s in soFar: return 0
            maxSplit = len(soFar)+1
            for partition in range(1, len(s)):
                a = s[:partition]
                b = s[partition:]
                if a not in soFar:
                    maxSplit = max(maxSplit, maxU(b, soFar|{a}))
            return maxSplit
        return maxU(s)


class Solution:
    def maxUniqueSplit(self, string: str) -> int:
        
        def split(s, splits):
            maxs = 1 if s not in splits else 0
            for i in range(1, len(s)):
                if s[:i] in splits:
                    continue
                rst = 1 + split(s[i:], splits+[s[:i]])
                maxs = max(rst, maxs)
            return maxs
        
        return split(string, [])

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        self.N=len(s)
        wordset=set(s)
        if len(wordset)>=self.N-1:
            return len(wordset)
        self.cur=0
        def dfs(i,visit,num):
            if self.N-i+num<=self.cur:
                return 
            if s[i:] not in visit:
                self.cur=max(self.cur,num+1)
            for j in range(i+1,self.N):
                new=s[i:j]
                if new not in visit:
                    visit.add(new)
                    dfs(j,visit,num+1)
                    visit.remove(new)
        visit=set()
        dfs(0,visit,0)
        return self.cur
            


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def check(st, cm):
            mx = 0 if st in cm else 1
            for i in range(1,len(st)):
                a = st[:i]
                b = st[i:]
                if a not in cm:
                    ncm = set(cm)
                    ncm.add(a)
                    c = check(b, ncm) + 1
                    if c > mx:
                        mx = c
            return mx

        return check(s, set())

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def explore(seen, s):
            for i in range(1, len(s)):
                word, other = s[:i], s[i:]
                if word in seen: continue
                explore(seen + [word], other)
            else:
                if s in seen:
                    self.res = max(len(seen), self.res)
                else:
                    self.res = max(len(seen) + 1, self.res)

        self.res = 0
        explore([], s)
        return self.res

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        self.mx = 0
        self.lim = len(s)
        def r(i,l,c):
            
            if i==self.lim-1:
                
                if s[i] not in l:
                    if c+1>self.mx:self.mx = c+1
                else:
                    if c>self.mx:self.mx = c
            else:
                for k in range(i+1,self.lim+1):
                    if k==self.lim:
                        if s[i:k] not in l:
                            if c+1>self.mx:self.mx = c+1
                    else:
                        if s[i:k] not in l:

                            r(k,l|{s[i:k]},c+1)
                    
                        
        r(0,set(),0)
        return self.mx


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        def dfs(i):
            nonlocal used, ret
            if i == n:
                ret = max(ret, len(used))
                return
            for j in range(i + 1, n + 1):
                w = s[i: j]
                if w in used:
                    continue
                used.add(w)
                dfs(j)
                used.discard(w)
        
        n = len(s)
        used = set()
        ret = 0
        dfs(0)
        return ret

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        @lru_cache(None)
        def helper(s):
            if not s:
                return [[]]
            
            splits = []
            for i in range(1, len(s) + 1):
                word = s[:i]
                next_splits = helper(s[i:])
                for split in next_splits:
                    if word not in split:
                        splits.append(split + [word])

            return splits
        ret = helper(s)
        max_len = max([len(x) for x in ret])
        return max_len

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        self.ans = 0
        n = len(s)
        def backtrack(start, have):
            if start>=n:
                self.ans=max(self.ans, len(have))
                return
            for i in range(start+1, n+1):
                tmp = s[start:i]
                if tmp in have: continue
                else:
                    have.add(tmp)
                    backtrack(i, have)
                    have.remove(tmp)
        backtrack(0, set())
        return self.ans


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        #if len(set(s)) == 1: return 1
        return self.dfs(s, 0, 1, set())
    
    def dfs(self, s, start, end, dic):
        if end>=len(s): return 0 if s[start:] in dic else 1
        k1 = 0
        if s[start:end] not in dic:
            dic.add(s[start:end])
            k1 = 1+self.dfs(s, end, end+1, dic)
            dic.remove(s[start:end])
        k2 = self.dfs(s, start, end+1, dic)
        return max(k1, k2)
        


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

        def dfs(start, seen):
            ans = 0
            if start == n:
                return ans

            for end in range(start + 1, n + 1):
                word = s[start:end]

                if word in seen:
                    continue

                seen.add(word)
                ans = max(ans, 1 + dfs(end, seen))
                seen.discard(word)

            return ans 
            
        return dfs(0, set())

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

    def helper(self, s, seen):
        ans = 0
        if s:
            for i in range(1, len(s) + 1):
                candidate = s[:i]
                if candidate not in seen:
                    seen.add(candidate)
                    ans = max(ans, 1 + self.helper(s[i:], seen))
                    seen.remove(candidate)
        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def builder(s, seen):
            if not s:
                return 0

            res = 0
            for i, c in enumerate(s):
                candidate = s[:i+1]
                if candidate not in seen:
                    seen.add(candidate)
                    res = max(res, 1 + builder(s[i+1:], seen))
                    seen.remove(candidate)
                    
            return res
        
        return builder(s, set())

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

    def helper(self, s, seen):
        ans = 0
        if s:
            for i in range(1, len(s) + 1):
                candidate = s[:i]
                if candidate not in seen:
                    seen.add(candidate)
                    ans = max(ans, 1 + self.helper(s[i:], seen))
                    seen.remove(candidate)
        return ans

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

    def helper(self, s, seen):
        ans = 0
        if s:
            for i in range(1, len(s) + 1):
                candidate = s[:i]
                if candidate not in seen:
                    seen.add(candidate)
                    ans = max(ans, 1 + self.helper(s[i:], seen))
                    seen.remove(candidate)
        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        seen = set()
        return self.helper(s, seen)
    
    def helper(self, s, seen):
        ans = 0
        if s:
            for i in range(1, len(s) + 1):
                candidate = s[:i]
                if candidate not in seen:
                    seen.add(candidate)
                    ans = max(ans, 1 + self.helper(s[i:], seen))
                    seen.remove(candidate)
        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        N = len(s)
        def splitLookup(ss, used): 
            Ns = len(ss)
            if ss in used: 
                maxSs = 0
            else: 
                maxSs = 1
            i = 1;
            while i < Ns and Ns-i > maxSs - 1: 
                sub = ss[:i]
                if sub not in used: 
                    Nsplit = splitLookup(ss[i:], used | {sub})
                    if Nsplit + 1 > maxSs: 
                        maxSs = Nsplit + 1
                i += 1
            return maxSs
        
        return splitLookup(s, set())


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def maxU(s, soFar=set()):
            if len(s) == 1 and s in soFar:
                return 0
            maxSplit = len(soFar)+1
            for partition in range(1, len(s)):
                a = s[:partition]
                b = s[partition:]
                print(a, b)
                if a not in soFar:
                    maxSplit = max(maxSplit, maxU(b, soFar|{a}))
            return maxSplit
        return maxU(s)

# import math

# class Solution(object):
#     def maxUniqueSplit(self, s):
#         \"\"\"
#         :type s: str
#         :rtype: int
#         \"\"\"
#         account = 0
#         solutions = set()
#         account = self.findSolutions(s, solutions)
#         print(\"finished\")
#         print(solutions)
#         print(account)
        
#         # if substring are the same than the solution is not right
#         # if one solution has more substring than another adopt this one
#         # could use divide and conqure to go done a string
        
#     def findSolutions(self, s, solutions):
#         strLen = len(s)
#         if strLen != 1:
#             halfPoint = math.ceil(strLen / 2) # use floor so that the left side is always smaller string
#             leftSubStr = s[:halfPoint]
#             rightSubStr = s[halfPoint:]
#             print(\"strlength is: {} mid point : {} left string: {} right string: {} \".format(strLen, halfPoint, leftSubStr, rightSubStr))
#             # only keep spliting when the substring is unique in solutions
#             if leftSubStr not in solutions:
#                 # remove previous solution if it is in it
#                 solutions.add(leftSubStr)
#                 return self.findSolutions(leftSubStr, solutions) + 1
#                 solutions.remove(leftSubStr)

#             if rightSubStr not in solutions:
#                 solutions.add(rightSubStr)
#                 return account + self.findSolutions(rightSubStr, solutions) + 1
#                 solutions.remove(rightSubStr)

#         else:
#             print(s)
#             return 1
        
class Solution:
    book = set()
    def maxUniqueSplit(self, s):
        result = 0
        for i in range(1, len(s)+1): #go through all the length of sub strings from left to right
            curr = s[:i]
            if curr not in self.book:
                self.book.add(curr) # add a type of sub string if it is not in it
                result = max(result, 1 + self.maxUniqueSplit(s[i:]))
                self.book.remove(curr)
        return result

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        self.ans=0
        seen=set()
        def search(i):
            if i==len(s):
                self.ans=max(len(seen),self.ans)
                return
            for j in range(i,len(s)):
                word=s[i:j+1]
                if word not in seen:
                    seen.add(word)
                    search(j+1)
                    seen.discard(word)
        search(0)
        return self.ans
            
                


def aux(s,lst,i):
    if(i == len(s)):
        return 0
    mx = 0
    for j in range(i,len(s)):
        #print(lst)
        if(s[i:j+1] not in lst):
            tmp = 1 + aux(s,lst+[s[i:j+1]],j+1)
            if tmp>mx:
                mx = tmp
    return mx

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        lst = []
        return aux(s,lst,0)

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        self.S = 0
        def dfs(s, tmp):
            if s == '': self.S = max(self.S, len(tmp))
            for i in range(1, len(s) + 1):
                if s[:i] not in tmp:
                    dfs(s[i:], tmp + [s[:i]])
        dfs(s, [])
        return self.S

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        return self.helper(s, set())
    
    def helper(self, s, set):
        if len(s) == 1 and s in set:
            return 0
        max_split = len(set) + 1
        
        for i in range(1, len(s)):
            a = s[:i]
            b = s[i:]
            max_split = max(max_split, self.helper(b, set|{a}))
        
        return max_split

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

        def dfs(i, cnt, visited):
            nonlocal ans, n
            if i == n:
                ans = max(ans, cnt)

            for j in range(i + 1, n + 1):
                if s[i:j] in visited:
                    continue
                visited.add(s[i:j])
                dfs(j, cnt + 1, visited)
                visited.remove(s[i:j])

        dfs(0, 0, set())  # function call
        return ans

class Solution:
    def __init__(self):
        self.ans = 0
        self.set = set()

    def maxUniqueSplit(self, s: str) -> int:
        self.solve(s, 0)
        return self.ans
    
    def solve(self, s: str, pos: int) -> None:
        if pos > len(s):
            return
        
        self.ans = max(self.ans, len(self.set))
        
        if self.ans - len(self.set) >= len(s) - pos:
            return
        
        for i in range(pos, len(s)):
            v = s[pos:i+1]
            if v in self.set:
                continue
            self.set.add(v)
            # print(self.set)
            self.solve(s, i + 1)
            self.set.remove(v)
            


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        ans, n = 0, len(s)
        def dfs(i, cnt, visited):
            nonlocal ans, n
            if i == n: ans = max(ans, cnt)      # stop condition
            for j in range(i+1, n+1):    
                if s[i:j] in visited: continue  # avoid re-visit/duplicates
                visited.add(s[i:j])             # update visited set
                dfs(j, cnt+1, visited)          # backtracking
                visited.remove(s[i:j])          # recover visited set for next possibility
        dfs(0, 0, set())                        # function call
        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        maximum=0
        seen=set()
        def dfs(idx,seen):
            if idx==len(s):
                nonlocal maximum
                maximum=max(len(seen),maximum)
                return
            for i in range(idx,len(s)):
                if s[idx:i+1] not in seen:
                    seen.add(s[idx:i+1])
                    dfs(i+1,seen)
                    seen.remove(s[idx:i+1])
            
        dfs(0,seen)
        return maximum
    
                
            


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        ret = 0
        
        def backtrack(start, currSet):
            if start == len(s):
                nonlocal ret
                ret = max(ret, len(currSet))
                return
        
            for i in range(start, len(s)):
                if s[start:i+1] not in currSet:
                    currSet.add(s[start:i+1])
                    backtrack(i+1, currSet)
                    currSet.remove(s[start:i+1])
        
        backtrack(0, set())
        return ret
                


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def numway(s):
            #if not s: return 0
            nw=0
            for i in range(1,len(s)+1):
                if s[:i] not in nq: 
                    nq.add(s[:i])
                    nw=max(nw,1+numway(s[i:]))
                    nq.remove(s[:i])
            return nw
        nq=set()
        return numway(s)

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def helper(curr_set, s):
            if len(s) == 0:
                return len(s)
            max_split = 0
            for i in range(len(s)):
                if s[:i+1] not in curr_set:
                    # curr_set2 = set(curr_set)
                    curr_set.add(s[:i+1])
                    max_split = max(max_split, 1 + helper(curr_set, s[i+1:]))
                    curr_set.remove(s[:i+1])
            return max_split
        return helper(set(), s)
        
        
        
#         curr_set = set()
#         i,j = 0,1
#         while j<=len(s):
#             if s[i:j] not in curr_set:
#                 curr_set.add(s[i:j])
#                 print(s[i:j])
#                 i, j = j, j+1
#             else:
#                 j += 1
        
#         return len(curr_set)


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        return get_max(s, set())
        
def get_max(s, set):
    maxi=0
    for i in range(1,len(s)+1):
        if s[:i] not in set:
            set.add(s[:i])
            # print(set)
            maxi=max(maxi, 1+get_max(s[i:],set))
            set.remove(s[:i])
            
    return maxi

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        self.res = 1

        def func(string: str, visited: set):
            if string in visited or len(string) == 0:
                return 0
            res = 1
            for i in range(len(string)):
                s = string[:i + 1]
                if s in visited:
                    continue
                visited.add(s)
                temp = func(string[i + 1:], visited) + 1
                visited.remove(s)
                res = max(res, temp)

            return res

        return func(s, set())

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        d = set()
        res = 1
        n = len(s)
        
        def solve(p, ans):
            nonlocal res
            if p == n:
                res = max(res, ans)
            for i in range(p, n):
                ss = ''.join(s[p:i+1])
                if ss in d: continue
                d.add(ss)
                solve(i + 1, ans + 1)
                d.remove(ss)
        
        solve(0, 0)
        return res
                


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def backtracking(ind):
            nonlocal ans
            if ind==len(s):
                ans = max(ans,len(split))
            
            for i in range(ind,len(s)):
                if s[ind:i+1] not in split:
                    split.add(s[ind:i+1])
                    backtracking(i+1)
                    split.remove(s[ind:i+1])
        
        ans = 0
        split = set()
        backtracking(0)
        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n = len(s) 
        def dp(i, cur):
            nonlocal ans            
            if len(cur) + n-i < ans: return
            if i >= n: ans = max(ans, len(cur))                
            l = n-i
            for k in range(1, l+1):
                cand = s[i:i+k]
                if cand not in cur: 
                    cur.append(cand)
                    dp(i+k, cur)
                    cur.pop()            
        ans, cur = 0, []
        dp(0, cur)
        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        self.result = []
        n = len(s)
        
        self.backtrack(s, 0, n, [])
                
        return len(max(self.result, key=len))
    
    
    def backtrack(self, s, left, n, currArr):
        
        if left >= n:
            self.result.append(currArr)
        
        for i in range(left, n):
            if s[left:i+1] in currArr:
                continue
            
            newArr = currArr.copy()
            newArr.append(s[left:i+1])
            
            self.backtrack(s, i+1, n, newArr)

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        '''
        result=set()
        i=0
        j=1
        
        while(i<len(s)):
            if s[i:j] not in result:
                if s[j:len(s)] in result:
                    result.add(s[i:])
                    break
                elif s[i:j]==s[j:len(s)]:
                    result.add(s[i:])
                    break
                else:
                    result.add(s[i:j])
                    i=j
                    j=i+1
            else:
                j+=1
        return len(result)
        '''
        seen=set()
        n=len(s)
        def dfs(i):
            if i==n:
                return 0
            res=1
            for j in range(i+1,n+1):
                if s[i:j] not in seen and s[j:] not in seen and s[i:j]!=s[j:]:
                    seen.add(s[i:j])
                    res=max(res,dfs(j)+1)
                    seen.remove(s[i:j])
            return res
        return dfs(0)


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def helper(s, start, seen):
            ans = 0
            for end in range(start + 1, len(s) + 1):
                added = s[start:end]
                print(added)
                if added not in seen:
                    seen.add(added)
                    ans = max(ans, 1 + helper(s, end, seen))
                    seen.remove(added)

            return ans
        seen = set()
        return helper(s, 0, seen)
                    


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        return self.dfs(s, 0, [])
    
    def dfs(self, s, index, ele):
        currMax = 0
        
        for i in range(index, len(s)):
            if s[index:i+1] not in ele:
                currMax = max(currMax, 1+self.dfs(s, i+1, ele[:] + [s[index:i+1]]))
            
        return currMax

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        self.cnt=0
        def getstring(start,visited):
            if start==len(s):
                self.cnt=max(self.cnt,len(visited))
                return
            
            for end in range(start+1,len(s)+1):
                temp=s[start:end]
                if temp in visited:
                    continue
                visited.add(temp)
                getstring(end,visited)
                visited.remove(temp)
        getstring(0,set())
        return self.cnt

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        if not s:
            return 0
        splits = [[] for _ in range(len(s))]
        for i, c in enumerate(s):
            splits[i].append(set([s[:i + 1]]))
            for j in range(1, i + 1):
                ss = s[j: i + 1]
                for spl in splits[j - 1]:
                    if ss not in spl:
                        splits[i].append(spl | set([ss]))
        return max([len(spl) for spl in splits[-1]])

from copy import deepcopy
class Solution:
    def __init__(self):    
        self.strings = []
    
    def maxUniqueSplit(self, s):
        
        n = len(s)
        result = []
        lookUp = set()
        
        self.dfs(s, lookUp, result)
        return len(self.strings)
        
    def dfs(self, s, lookUp, result):
        
        if len(s) == 0:
            if len(result) > len(self.strings):
                self.strings[:] = result
            return
        
        for i in range(0, len(s)):
            if s[0:i+1] not in lookUp:
                lookUp.add(s[0:i+1])
                result.append(s[0:i+1])
                self.dfs(s[i+1:], lookUp, result)
                lookUp.remove(s[0:i+1])
                result.pop()

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def backtracking(ind):
            nonlocal ans
            if ind==len(s):
                ans = max(ans,len(split))
            
            for i in range(ind,len(s)):
                if s[ind:i+1] not in split:
                    split.append(s[ind:i+1])
                    backtracking(i+1)
                    split.remove(s[ind:i+1])
        
        ans = 0
        split = []
        backtracking(0)
        return ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        self.ans = 0
        seen = set()
        
        def dp(i):
            if i == len(s):
                self.ans = max(self.ans, len(seen))
            
            for j in range(i, len(s)):
                word = s[i:j+1]
                if word not in seen:
                    seen.add(word)
                    dp(j+1)
                    seen.discard(word)
                    
        dp(0)
        return self.ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:        
        def dfs(i, vis):
            nonlocal ans            
            if len(vis) + n-i < ans: return
            if i >= n: ans = max(ans, len(vis))                
            l = n-i
            for k in range(1, l+1):
                x = s[i:i+k]
                if x not in vis: 
                    vis.add(x)
                    dfs(i+k, vis)
                    vis.discard(x)
        ans, n, vis = 0, len(s), set()
        dfs(0, vis)
        return ans

class Solution:
    def __init__(self):    
        self.strings = []
    
    def maxUniqueSplit(self, s):
        
        n = len(s)
        result = []
        lookUp = set()
        
        self.dfs(s, lookUp, result)
        return len(self.strings)
        
    def dfs(self, s, lookUp, result):
        
        if len(s) == 0:
            if len(result) > len(self.strings):
                self.strings[:] = result
            return
        
        for i in range(0, len(s)):
            if s[0:i+1] not in lookUp:
                lookUp.add(s[0:i+1])
                result.append(s[0:i+1])
                self.dfs(s[i+1:], lookUp, result)
                lookUp.remove(s[0:i+1])
                result.pop()

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        self.ans = 0
        def dfs(node,seen):
            if node == len(s):
                self.ans = max(self.ans,len(seen))
            for i in range(node,len(s)):
                if s[node:i+1] not in seen:
                    dfs(i+1,seen|{s[node:i+1]})
        dfs(0,set())
        return self.ans

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        
        
        def backtrack(m, s):
            if len(s) == 0:
                return 0
            ans = 0
            for i in range(1, len(s) + 1):
                candidate = s[:i]
                if candidate not in m:
                    m.add(candidate)
                    ans = max(ans, 1 + backtrack(m, s[i:]))
                    m.remove(candidate)
                    
            return ans
    
        m = set()
        
        return backtrack(m, s)

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        self.max = 0
        self.backtrack(s,set(),0)
        return self.max
        
    def backtrack(self,s,store,l):
        if l >=len(s):
            self.max = max(self.max,len(store))        
        for i in range(l,len(s)+1):
            if s[l:i] not in store and l!=i:
                store.add(s[l:i])
                self.backtrack(s,store,i)
                store.remove(s[l:i])
    


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        return self.dp(s,0,0,[])
        
    def dp(self,s,start,pos,ans):
        if pos == len(s):
            return len(ans)
        a = 0
        b = self.dp(s,start,pos+1,list(ans))
        if s[start:pos+1] not in ans:
            ans.append(s[start:pos+1])
            a = self.dp(s,pos+1,pos+1,list(ans))
            # ans.pop()
        # ans.remove(s[start:pos+1])
        
        return a if a > b else b
        # return ans


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n = len(s)
        
        self.res = 0
        
        def helper(curIdx, curW, curSets):
            if (curIdx == n):
                self.res = max(self.res, len(curSets))
                return
            
            #don't split
            helper(curIdx+1, curW+s[curIdx], curSets)
            
            #split
            if (curW+s[curIdx] not in curSets):
                helper(curIdx+1, '', curSets | {(curW+s[curIdx])})
                
        helper(0, '', set())
        
        return self.res

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        return self.dp(s,0,0,[])
        
    def dp(self,s,start,pos,ans):
        if pos == len(s):
            return len(ans)
        a = 0
        b = self.dp(s,start,pos+1,list(ans))
        if s[start:pos+1] not in ans:
            ans.append(s[start:pos+1])
            a = self.dp(s,pos+1,pos+1,list(ans))
            ans.pop()
        # ans.remove(s[start:pos+1])
        
        return a if a > b else b
        # return ans