題目

當一個字符串 s 包含的每一種字母的大寫和小寫形式 同時 出現在 s 中，就稱這個字符串 s 是 美好 字符串。比方說，“abABB” 是美好字符串，因為 ‘A’ 和 ‘a’ 同時出現了，且 ‘B’ 和 ‘b’ 也同時出現了。然而，“abA” 不是美好字符串因為 ‘b’ 出現了，而 ‘B’ 沒有出現。
給你一個字符串 s ，請你返回 s 最長的 美好子字符串 。如果有多個答案，請你返回 最早 出現的一個。如果不存在美好子字符串，請你返回一個空字符串。
示例 1：
輸入：s = “YazaAay”
輸出：“aAa”
解釋：“aAa” 是一個美好字符串，因為這個子串中僅含一種字母，其小寫形式 ‘a’ 和大寫形式 ‘A’ 也同時出現了。
“aAa” 是最長的美好子字符串。
示例 2：
輸入：s = “Bb”
輸出：“Bb”
解釋：“Bb” 是美好字符串，因為 ‘B’ 和 ‘b’ 都出現了。整個字符串也是原字符串的子字符串。
示例 3：
輸入：s = “c”
輸出：""
解釋：沒有美好子字符串。
示例 4：
輸入：s = “dDzeE”
輸出：“dD”
解釋：“dD” 和 “eE” 都是最長美好子字符串。
由于有多個美好子字符串，返回 “dD” ，因為它出現得最早。
提示：
1 <= s.length <= 100
s 只包含大寫和小寫英文字母。
來源：力扣（LeetCode）

解題思路

??一般而言，查找子序列，子字符串這種連續的子集時往往都可以使用滑動窗口作為突破點。題目的意思是一個美好子字符串中如果含有一個小寫字母那么必須含有一個相應的大寫字母，所以我們可以建立兩個集合一個包含大寫字母，一個包含小寫字母如果大寫字母集合和小寫字母集合相等，那么它們所反映的子字符串就是美好字符串。
??如果把整個字符串的大小寫集合做一個交集，那么交集里的所有組成的子字符一定是最長的美好子字符串，但是反應在題目所給的字符串s中可不一定是連續的，所以這樣也不能稱之為字符串，但是這是一個非常重要的信息，意味著如果有最長的美好子字符串，那么它的長度一定不會超過交集里所有元素之和；同樣意味著滑動窗口的長度最大也就是這樣了。
??鑒于題目是找最長的字串，那么我們選擇最大的滑動窗口慢慢縮小來找符合條件的子字符串。維護一個小寫字母集合，再維護一個大寫字母集合，每移動一次就更新集合里的值，直到兩個集合相等，那么就能找到最長美好子字符串了。
??以示例1為例：大小寫字母集合的交集為{‘y’, ‘a’}，那么窗口的最長長度就是6(y有2個a有4個)，窗口一開始就包含了s的前6個元素"YazaAa"，然后查看大小寫字符種類的交集，發現不相等，則窗口往右移動變為"azaAay"，發現也不成立。此時如果想要更方便的維護窗口其實可以將窗口減少一個元素(“a”)之后再往左移動，移動到最左端的過程中發現仍未成立可以再減少一個元素(“y”)再接著往右移動，如此往復循環，但是題目條件有一個限定多個美好字符串出現的話要返回靠左的字符串，那么我們只能一遍一遍從左往右移動，并且每次只刪除最右邊的元素，在移動的過程中一旦條件成立，那么就是最長的美好子字符串，因為我們的窗口是從大往小縮的。

class Solution:def longestNiceSubstring(self, s: str) -> str:upper={}  lower={}for i in s:if i.islower():lower[i]=lower.get(i,0)+1else:upper[i.lower()]=upper.get(i.lower(),0)+1maxcom=upper.keys()&lower.keys()  #查看最長子字符串的可能包含元素if upper.keys()==lower.keys():return smaxLenth=0  #子字符串最長的可能for i in maxcom:maxLenth+=lower[i]+upper[i]upper={}lower={}for i in s[0:maxLenth]:if i.islower():lower[i]=lower.get(i,0)+1else:upper[i.lower()]=upper.get(i.lower(),0)+1UPPER=copy.deepcopy(upper)  #維護最左端的原始窗口LOWER=copy.deepcopy(lower)i=0  #窗口兩端的指針j=maxLenth-1def move(i,j): #移動窗口if lower.keys()==upper.keys():return i,j+1while j+1<len(s):#右移的過程中刪除第一個元素if s[i].islower():lower[s[i]]-=1if lower[s[i]]==0:del lower[s[i]]else:upper[s[i].lower()]-=1if upper[s[i].lower()]==0:del upper[s[i].lower()]i+=1j+=1#右移的過程中添加左端新來的元素if s[j].islower():lower[s[j]]=lower.get(s[j],0)+1else:upper[s[j].lower()]=upper.get(s[j].lower(),0)+1if lower.keys()==upper.keys():return i,j+1return -1,-1while j>0:a,b=move(i,j)if a!=-1:return s[a:b]#如果在一遍移動中未發現符合條件的字串那么窗口縮小一個單位，刪除原始窗口最右邊的元素if s[maxLenth-1].islower():LOWER[s[maxLenth-1]]-=1if LOWER[s[maxLenth-1]]==0:del LOWER[s[maxLenth-1]]else:UPPER[s[maxLenth-1].lower()]-=1if UPPER[s[maxLenth-1].lower()]==0:del UPPER[s[maxLenth-1].lower()]lower=copy.deepcopy(LOWER)upper=copy.deepcopy(UPPER)maxLenth-=1  #最長的可能減小1個單位j=maxLenth-1  #窗口兩端指針復位i=0return ""

總結

以上是生活随笔為你收集整理的LeetCode简单题之最长的美好子字符串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。