# 1593. Split a String Into the Max Number of Unique Substrings """ 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 origin string. however, you must split the substrings such that all of them are unique. a substring is a contiguous sequence of characters within a string. """ class Solution(object): def maxUniqueSplit(self, s): """ :type s: str :rtype: int """ def backtrack(beg, vis): if beg == len(s): return 0 max_split = 0 for end in range(beg + 1, len(s) + 1): substr = s[beg:end] if substr not in vis: vis.add(substr) max_split = max(max_split, backtrack(end, vis) + 1) vis.remove(substr) return max_split return backtrack(0, set()) if __name__ == "__main__": obj = Solution() print(obj.maxUniqueSplit(s="ababccc")) print(obj.maxUniqueSplit(s="aba")) print(obj.maxUniqueSplit(s="aa"))