Posted on 2023-07-09 18:54
Uriel 閱讀(37)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
求一個字符串的子串，使得其中字母的出現次數最大最小值差距最大（子串需要下標連續?。?br />DP，思路參考 -> https://leetcode.com/problems/substring-with-largest-variance/solutions/2579443/python-3-solution-kadanes/
1 #2272
2 #Runtime: 5894 ms (Beats 50%)
3 #Memory: 13.9 MB (Beats 20%)
4
5 class Solution(object):
6 def largestVariance(self, s):
7 """
8 :type s: str
9 :rtype: int
10 """
11 f1, f2, ans = 0, 0, 0
12 pairs = [(x, y) for x in set(s) for y in set(s) if x != y]
13 for _ in range(2):
14 for p in pairs:
15 for l in s:
16 if l not in p:
17 continue
18 if l == p[0]:
19 f1 += 1
20 elif l == p[1]:
21 f2 += 1
22 if f1 < f2:
23 f1, f2 = 0, 0
24 elif f1 and f2:
25 ans = max(ans, f1 - f2)
26 f1, f2 = 0, 0
27 s = s[::-1]
28 return ans