題目

在第一人稱射擊游戲中，玩家通過鍵盤的A、S、D、W四個按鍵控制游戲人物分別向左、向后、向右、向前進行移動，從而完成走位。

假設玩家每按動一次鍵盤，游戲人物會向某個方向移動一步，如果玩家在操作一定次數的鍵盤并且各個方向的步數相同時，此時游戲人物必定會回到原點，則稱此次走位為完美走位。

現給定玩家的走位（例如：ASDA）,請通過更換其中一段連續走位的方式使得原走位能夠變成一個完美走位。其中待更換的連續走位可以是相同長度的任何走位。

請返回待更換的連續走位的最小可能長度。若果原走位本身是一個完美走位，則返回0。

輸入

輸入為由鍵盤字母表示的走位s，例如：ASDA

輸出

輸出為待更換的連續走位的最小可能長度

備注

走位長度1 ≤ s.length ≤ 10^5

s.length是4的倍數

s中只含有A,S,D,W四種字符

示例一

輸入

ASDW

輸出

0

說明

已經是完美走位了。

示例二

輸入

AASW

輸出

1

說明

需要把一個A更換成D，這樣可以得到ADSW或者DASW。

示例三

輸入

AAAA

輸出

3

說明

可以替換后3個A，得到ASDW。

示例四

輸入

AAAAADDD

輸出

4

解題思路

“

注意，本題和LC76. 最小覆蓋子串幾乎完全一致。重點在于如何將原問題轉化為覆蓋子串的問題。

”

題目有兩個重要條件：

完美走位字符串是指字符串中A、S、D、W四種字符出現次數相等的字符串

s.length是4的倍數

對于長度為len(s)的原字符串s來說，為了使其轉變為一個完美走位字符串，其中A、S、D、W四種字符出現次數應該均為num = len(s) // 4。

原字符串s中各個字符出現的次數可以用哈希表cnt_s = Counter(s)進行統計，對于出現次數多于num = len(s) // 4的字符ch，應該修改cnt_s[ch] - len(s) // 4個字符為其他出現次數少于num = len(s) // 4的字符，才能夠使得s變為一個完美走位字符串。

以示例四為例，s = "AAAAADDD"，字符"A"出現的次數為5，字符"D"應該修改3，而num = len(s) // 4 = 2，需要修改3個"A"和1個"D"為剩余兩種字符，才能使得s變為完美走位字符串。故我們需要找到包含3個"A"和1個"D"的最小子串。

因此這個問題就轉變為了，找到覆蓋cnt_s[ch] - len(s) // 4個的字符ch（ch滿足條件cnt_s[ch] > len(s) // 4）的最短子串。需要覆蓋的子串中所出現的字符以及次數，可以用另一個哈希表cnt_sub儲存。

那么這個問題就和LC76. 最小覆蓋子串完全一致了。上述邏輯整理為代碼即

num=len(s)//4
cnt_s=Counter(s)
cnt_sub={k:v-numfork,vincnt_s.items()ifv>num}

代碼

#題目：2023Q1A-完美走位
#分值：100
#作者：許老師&&吳師兄學算法
#算法：不定滑窗
#代碼看不懂的地方，請直接在群上提問


fromcollectionsimportCounter
frommathimportinf


#定義輔助函數check()
#用于檢查cnt_sub中的各個字符是否出現在cnt_win中，
#且cnt_win中的個數大于等于cnt_sub
defcheck(cnt_win,cnt_sub):
returnall(cnt_win[k]>=cnt_sub[k]forkincnt_sub)


s=input()
num=len(s)//4
#獲得原字符串中所有字符的出現次數
cnt_s=Counter(s)
#獲得需要覆蓋的子串的字符以及出現次數
cnt_sub={k:v-numfork,vincnt_s.items()ifv>num}

#如果cnt_sub長度為0，說明每一種字符出現次數相等
#s已經是一個完美走位字符串，輸出0
iflen(cnt_sub)==0:
print(0)
#否則要進行類似LC76.最小覆蓋子串的不定滑窗過程
else:
#初始化滑窗對應的哈希表、最小覆蓋的窗口長度
cnt_win=Counter()
ans=inf
left=0

forright,chinenumerate(s):
# Q1：對于每一個右指針right所指的元素ch，做什么操作？
# A1：將其加入哈希表cnt_win的計數中
cnt_win[ch]+=1
# Q2：什么時候要令左指針left右移？在什么條件下left停止右移？【循環不變量】
# A2：check(cnt_win, cnt_sub)為True，left可以右移以縮小窗口長度
whilecheck(cnt_win,cnt_sub):
# Q3：什么時候進行ans的更新？
# A3：check(cnt_win, cnt_sub)為True
ans=min(ans,right-left+1)
cnt_win[s[left]]-=1
left+=1

print(ans)

時空復雜度

時間復雜度：O(N)。僅需一次遍歷整個字符串s。

空間復雜度：O(1)。只有4種字符，哈希表所占用空間為常數級別空間。

審核編輯：湯梓紅