split_string_max_unique_substr.py (1199B)
| # 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"))
|
