給出一個(gè)字符串,問(wèn)最少切分成幾個(gè)子串可以保證每個(gè)子串的每個(gè)字符都不相同,hash,用python set很方便
1 #2405
2 #Runtime: 105 ms (Beats 70.83%)
3 #Memory: 14.8 MB (Beats 95.83%)
4
5 class Solution(object):
6 def partitionString(self, s):
7 """
8 :type s: str
9 :rtype: int
10 """
11 ans = 1
12 ch_set = set()
13 for i in s:
14 if i in ch_set:
15 ch_set = set()
16 ans += 1
17 ch_set.add(i)
18 return ans