求助一道shortest balanced substring的题！

Jay16 发表于 2021-1-7 09:47
非常感谢这么详细的解答。感激！

while i <= lastseen[c] 其实是错的，我刚刚自己构造了一个反例 "acdCAcD". 更新一下，末尾给了几个 test case.

1. def shortestBalanecdSubstring(s):
   
2.     count = collections.Counter()
   
3.     lastseen = collections.defaultdict(lambda :-1)
   
4.     i = 0
   
5.     ans = math.inf
   
6.     res = ''
   
7.     for j, c in enumerate(s):
   
8.         count[c] += 1
   
9.         C = c.swapcase()
   
10.         if count[C] == 0 or lastseen[C] < lastseen[c]:
    
11.             lastseen[c] = j
    
12.             continue
    
13.         while i < lastseen[s[i]] or i <= j - ans + 1:
    
14.             count[s[i]] -= 1
    
15.             i += 1
    
16.         count2 = +count
    
17.         for k in range(i, lastseen[C]+1):
    
18.             if all(count2[c.swapcase()] for c in count2 if count2[c]):
    
19.                 res = s[k:j+1]
    
20.                 ans = j-k+1
    
21.             count2[s[k]] -= 1
    
22.         lastseen[c] = j
    
23.     return res
    
24. 
    
25. shortestBalanecdSubstring("ABaBcabC")
    
26. shortestBalanecdSubstring("acdCAcD")
    
27. s = "".join([random.choice(string.ascii_letters) for _ in range(20000)])
    
28. shortestBalanecdSubstring(s)
    

复制代码

感觉可以参考下 刷题网 395.
比较快的一个解题思路就是  利用一个隐含条件：只有26中字母， 然后结合双指针大法之追赶法。
时间复杂度 O(26*N)

ytx2013 发表于 2021-1-7 14:19
感觉可以参考下 刷题网 395.
比较快的一个解题思路就是  利用一个隐含条件：只有26中字母， 然后结合双指 ...

比你想的复杂，Substring 如果不到 K Repeating Characters 你把窗口缩短以后更不会到。但如果 substring is not balanced, 缩短以后有可能变成 balanced 的，所以比一般的 sliding window 恶心点。

sylvia2010 发表于 2021-1-7 15:09
比你想的复杂，Substring 如果不到 K Repeating Characters 你把窗口缩短以后更不会到。但如果 substring ...

要不给几个反例试试看？

btw, 我说的是参考这个思路
https://leetcode.com/problems/lo ... 87739/Java-Strict-O(N)-Two-Pointer-Solution

ytx2013 发表于 2021-1-7 15:34
要不给几个反例试试看？

btw, 我说的是参考这个思路

你不写出来我怎么给反例啊，你先试试 aBBBBBBBBBBBBBB...AAAAAAAAAAAAAAAAAAb 这种。

可以用类似于prefix sum的思路做。
prefixSum[i][char] 表示字符串前i个字符里面，大写的char的比小写的char多出现多少次（可以是负数）。其中0&lt;=i&lt;=n，’a’&lt;=char&lt;=‘z’。

再用一个map来存key: prefixSum[i] -&gt; value: i (注：这里的prefixSum[i]是一个长度为26的数组，Java里我们可以用ArrayList)

i 从0开始一直到n，当往map里放key: prefixSum[i] -&gt; value: i，如果发现map已经存在和prefixSum[i]相等key，那就用i减去已有的key对应的value，如果差值小于当前ans，就update当前answer。

ytx2013 发表于 2021-1-7 14:19
感觉可以参考下 刷题网 395.
比较快的一个解题思路就是  利用一个隐含条件：只有26 ...

哈哈什么双指针大法哈哈哈

readman 发表于 2021-1-6 00:03
shortest?? 真的吗? 空string难道不是满足题意的答案么?

这个疑问确实我的题里没说清楚

ytx2013 发表于 2021-1-7 14:19
感觉可以参考下 刷题网 395.
比较快的一个解题思路就是  利用一个隐含条件：只有26中字母， 然后结合双指 ...

确实leetcode讨论区也给出一个26n的解法，这种应该才是最优的，谢谢题号，我去做一下启发下思路

ytx2013 发表于 2021-1-7 14:19
感觉可以参考下 刷题网 395.
比较快的一个解题思路就是  利用一个隐含条件：只有26中字母， 然后结合双指 ...

你说的隐含条件 - 只有26中字母，这个特别对