求助一道shortest balanced substring的题！

A string is considered balanced when every letter in the string appears both in uppercase and lowercase
For example, CATattac is balanced (a, c, t occur in both cases). Madam is not (a, d only appear in lowercase).
Write a function that given a string returns the shortest balanced substring of that string.
Can this be solved with a sliding window approach?
Update:
More examples
“azABaabza” returns “ABaab”
“TacoCat” returns -1 (not balanced)
“AcZCbaBz” returns the entire string

没找到原题，如果有人知道是哪个平台原题求告知！
除了暴力n平方算法完全想不出其他思路，怎么用sliding window呢？
https://leetcode.com/discuss/int ... t-or-OA-or-Codility

这个帖子里有一些讨论大家可以参考一下，但是一个高赞回答似乎也不完全对。
求助！


补充内容 (2021-1-7 17:33):
回复都加米！

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

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

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

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

得，脸都快被打肿了才写出来。

Sliding window 还是适合有一定 “单调性” 的问题，这个其实没那么合适，最后强行 sliding window. 注意这里如果不存在 balanced substring 我返回的是空 string (原题要求返回 -1)。

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[c] or 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
    

复制代码

[/i][/i]

补充内容 (2021-1-7 10:19):
刚发现 while i <= lastseen[c] or i < lastseen[s[\i]] or i <= j - ans + 1: 那行是错的，改成 while i < lastseen[s[\i]] or i <= j - ans + 1: 就好了。

这个很明显 sliding window 啊，i = 0, for j, c in enumerate(s)... 用个 counter 数 letters.

sliding window 求 shortest 简单讲就是，慢慢增加 j（增大 window）, 直到满足条件，然后增加 i (缩小 window) 直到条件不满足，在不满足之前每次都更新 answer. 最后 return answer. 复杂度 O(n). 等我睡醒帮你写一个吧。

sylvia2010 发表于 2021-1-5 17:45
这个很明显 sliding window 啊，i = 0, for j, c in enumerate(s)... 用个 counter 数 letters.

slidin ...

啊啊这是哪里来的小天使还帮我写！谢谢集美！等你睡醒后讨论哈
你讲的sliding window基本思路好清楚，但是我不太确定这个sliding window是不是要从每一个位置开始尝试？因为给定string里可能有多个balanced substring，不是只有一个balanced substring。比如abABcC，用sliding window找到第一个balanced substring - abAB后，怎么办呢？怎么移动窗口呢？应该移动到从b开始吧？这样的话好像还是n平方呢...

shortest?? 真的吗? 空string难道不是满足题意的答案么?

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

那就把题意改的更明确一点，返回不为空的shortest balanecd substring...

北极兔兔鲨 发表于 2021-1-6 00:14
那就把题意改的更明确一点，返回不为空的shortest balanecd substring...

呵呵, 俺也等那个小天使的code

sylvia2010 发表于 2021-1-7 04:55
得，脸都快被打肿了才写出来。

Sliding window 还是适合有一定 “单调性” 的问题，这个其实没那么合适 ...

感谢小天使。请问能麻烦解释一下
if count[C] == 0 or lastseen[C] < lastseen[c]

和

while i <= lastseen[c] or i < lastseen[s[i]] or i <= j - ans + 1:

吗？

谢谢

Jay16 发表于 2021-1-7 08:39
感谢小天使。请问能麻烦解释一下
if count[C] == 0 or lastseen[C] < lastseen[c]

积分终于到 188 了 噢耶。“强行” sliding window 嘛，给你讲讲具体的思路：

我们观察 s[i:j+1] (也就是从 s[\i] 到 s[j]), 在看到 s[j] 的时候只找 s[j] 结尾的最短的 balanced substring. 注意两个要求有先后之分，首先 s[j] 结尾，其次最短。

a) 如果 count[C] == 0, 那你窗口里没有能跟 s[j] 匹配上的，所以没有任何 balanced substring, 直接看下一个。
b) 如果 lastseen[C] < lastseen[c], 那这个 substring 长这样 --------C--------c----------c 你可以看到如果这里有一个 balanced substring 那去掉末尾这个 c 也是 balanced 的，所以这个也不是我们想要的。

以上两点是什么时候你可以 extend window (增大 j, substring 变长). 这题麻烦的地方在下面，什么时候可以缩短 window (增大 i, 缩小你观察的 substring.) ，我只找到了两种比较 tricky 的办法。

a) while i <= lastseen[c] 理由跟上面类似，你现在的 substring 长这样 --------c-----------c 如果有 balanced substring 包含前面那个 c，并以后面这个 c 结尾, 那去掉后面那个 c 也是 balanced 的，这种情况在之前已经考虑过了，所以我们缩短窗口。
b) i < lastseen[s[\i]] 也差不多，如果现在的 substring 长这样 c-------------c------------ 那去掉前面这个 c 不影响 最短的 balanced substring（这里建议仔细想想，只能去掉开头和中间重复的，不能去掉里面重复的，比如 Abaab 这种，不能缩短。）
c) i <= j - ans + 1 这个比较简单，如果我们已经找到一个答案 ans 了，就没必要关注太长的窗口了，赶紧缩短。

---------------------------

之前写出来没讲复杂度，因为我不是特别确定 worst case. 一般 sliding windows 都可以做到 O(n) 因为 i, j 都在增加。但这里有个 for k in range(i, lastseen[C]+1), 所以稍微别扭一点。但平均是 O(n) 的（对于充分长的 string, 几乎一定能找到形如 "uU" 的 substring 然后剩下的过程中窗口长度就最多是 2 所以对这些情形总是线性的）。如果你能构造一个 O(n2) 的 worst case 不妨发出来。

sylvia2010 发表于 2021-1-7 09:06
积分终于到 188 了 噢耶。“强行” sliding window 嘛，给你讲讲具体的思路：

我们观察 s (也就是从 s ...

非常感谢这么详细的解答。感激！