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.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Complete search

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:

		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])
					followup = helper(i)
					res = max(res, 1 + followup)
					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)


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) -> 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:
			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:
					d.add(s[l:r])
					maxl = self.bt(s, d, r, maxl)
					d.remove(s[l:r])
			return maxl


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 __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 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):
			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)
		return cache[i]


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:
				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)
		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
			for i in range(1, len(s) + 1):
				if s[0:i] not in visiting:
					visiting.add(s[0:i])
					currli.append(s[0:i])
					dfs(i, s[i:])
					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])
			dfs(i, s[i:])
			currli.pop()
			visiting.remove(s[0:i])
		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))
		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
			elif 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])
				res = dfs(temp, s[i:], res)
				temp.pop()
			return res
		return len(dfs([], s, []))


class Solution:

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

		def backtrack(seen, sidx):
			if sidx == len(s):
				self.res = max(self.res, len(seen))
				return
			if len(seen) + len(s) - sidx <= self.res:
				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 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:
		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:
		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())


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 = 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)
		ret = 1
		for comb in combinations:
			if len(comb) == len(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:
		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 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


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


import collections
import itertools

class Solution:

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

		def check(b):
			h = {}
			w = ''
			b = list(b) + [0]
			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):
			n = check(b)
			ans = max(ans, n)
		return ans


class Solution:

	def maxUniqueSplit(self, s: str) -> int:
		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:
		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)]
		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):
			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)
				maxres = max(maxres, len(sett))
		return maxres


class Solution:

	def maxUniqueSplit(self, s: str) -> int:
		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:
		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)
		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)
			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 = []
			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)))))


from itertools import combinations

class Solution:

	def maxUniqueSplit(self, s: str) -> int:
		for num_splits in reversed(range(1, len(s))):
			num_strings = num_splits + 1
			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
		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):
			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)
		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)
		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):
			ts = set()
			cs = ''
			for i in range(len(s)):
				cs += s[i]
				if n % 2 == 1:
					if cs in ts:
						return -1
					else:
						ts.add(cs)
						cs = ''
					n = n // 2
				else:
					n = n // 2
					continue
			if cs != '':
				if cs in ts:
					return -1
				else:
					ts.add(cs)
			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


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, 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
			res = split(s, bb)
			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:
		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


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)
				if not ok:
					break
			if not ok:
				continue
			tmp = s[prev:]
			if tmp not in 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):
			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:])
	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
			ans = max(ans, len(subs) + 1)
		return ans


class Solution:

	def maxUniqueSplit(self, s: str) -> int:
		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:
		from collections import defaultdict
		self.ans = 1

		def get(s, l, n):
			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 = ''
			for j in range(i, len(s)):
				cur += s[j]
				get(s, l + [cur], j + 1)
		get(s, [], 0)
		return self.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]
				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()

		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:
		(N, res) = (len(s), 0)
		for i in range(2 ** (N - 1)):
			(start, seen) = (0, set())
			for j in range(N):
				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])
			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
		ps = all_partitions(s)
		ret = 0
		for p in ps:
			l = list(dict.fromkeys(p))
			if len(p) == len(l):
				ret = max(ret, len(p))
		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
			while True:
				try:
					idx = mask.index('1', begin)
					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'))
		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'
			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
			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)
			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)
		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)
			cand = [s[0]]
			for (i, x) in enumerate(bit):
				if x == '0':
					cand[-1] += s[i + 1]
				else:
					cand.append(s[i + 1])
			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)


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))
			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)
		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)):
				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:
			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)):
			bb = '{0:0' + str(m - 1) + 'b}'
			b = bb.format(i)
			st = 0
			l = []
			for k in range(len(b)):
				if b[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])
			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:

		def dfs(index, visited):
			nonlocal ans
			if s[index:n] and s[index:n] not in visited:
				ans = max(ans, len(visited) + 1)
			for i in range(index, n):
				if s[index:i] and s[index:i] not in visited and (len(visited) + 1 + n - i > ans):
					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:

	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)


from functools import lru_cache

def _helper(s: str, visited) -> int:
	n = len(s)
	result = 0
	for i in range(n - 1):
		(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)
	if not s in visited:
		result = max(result, 1)
	return result

class Solution:

	def maxUniqueSplit(self, s: str) -> int:
		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
				elif 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
					elif 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:
		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:

		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:
		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:
	book = set()

	def maxUniqueSplit(self, s):
		result = 0
		for i in range(1, len(s) + 1):
			curr = s[:i]
			if curr not in self.book:
				self.book.add(curr)
				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)):
		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())
		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)
			self.solve(s, i + 1)
			self.set.remove(v)


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):
			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_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)


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])
			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:
		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:

		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


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 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 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))
		return a if a > b else b


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
			helper(curIdx + 1, curW + s[curIdx], curSets)
			if curW + s[curIdx] not in curSets:
				helper(curIdx + 1, '', curSets | {curW + s[curIdx]})
		helper(0, '', set())
		return self.res