diff options
Diffstat (limited to 'split_string_max_unique_substr.py')
-rw-r--r-- | split_string_max_unique_substr.py | 39 |
1 files changed, 39 insertions, 0 deletions
diff --git a/split_string_max_unique_substr.py b/split_string_max_unique_substr.py new file mode 100644 index 0000000..354e9c8 --- /dev/null +++ b/split_string_max_unique_substr.py @@ -0,0 +1,39 @@ +# 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")) |