算法面試真題：完美走位

題目

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

假設(shè)玩家每按動(dòng)一次鍵盤，游戲人物會向某個(gè)方向移動(dòng)一步，如果玩家在操作一定次數(shù)的鍵盤并且各個(gè)方向的步數(shù)相同時(shí)，此時(shí)游戲人物必定會回到原點(diǎn)，則稱此次走位為完美走位。

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

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

輸入

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

輸出

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

備注

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

s.length是4的倍數(shù)

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

示例一

輸入

ASDW

輸出

0

說明

已經(jīng)是完美走位了。

示例二

輸入

AASW

輸出

1

說明

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

示例三

輸入

AAAA

輸出

3

說明

可以替換后3個(gè)A，得到ASDW。

示例四

輸入

AAAAADDD

輸出

4

解題思路

“

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

”

題目有兩個(gè)重要條件：

完美走位字符串是指字符串中A、S、D、W四種字符出現(xiàn)次數(shù)相等的字符串

s.length是4的倍數(shù)

對于長度為len(s)的原字符串s來說，為了使其轉(zhuǎn)變?yōu)橐粋€(gè)完美走位字符串，其中A、S、D、W四種字符出現(xiàn)次數(shù)應(yīng)該均為num = len(s) // 4。

原字符串s中各個(gè)字符出現(xiàn)的次數(shù)可以用哈希表cnt_s = Counter(s)進(jìn)行統(tǒng)計(jì)，對于出現(xiàn)次數(shù)多于num = len(s) // 4的字符ch，應(yīng)該修改cnt_s[ch] - len(s) // 4個(gè)字符為其他出現(xiàn)次數(shù)少于num = len(s) // 4的字符，才能夠使得s變?yōu)橐粋€(gè)完美走位字符串。

以示例四為例，s = "AAAAADDD"，字符"A"出現(xiàn)的次數(shù)為5，字符"D"應(yīng)該修改3，而num = len(s) // 4 = 2，需要修改3個(gè)"A"和1個(gè)"D"為剩余兩種字符，才能使得s變?yōu)橥昝雷呶蛔址９饰覀冃枰业桨?個(gè)"A"和1個(gè)"D"的最小子串。

因此這個(gè)問題就轉(zhuǎn)變?yōu)榱?，找到覆蓋cnt_s[ch] - len(s) // 4個(gè)的字符ch（ch滿足條件cnt_s[ch] > len(s) // 4）的最短子串。需要覆蓋的子串中所出現(xiàn)的字符以及次數(shù)，可以用另一個(gè)哈希表cnt_sub儲存。

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

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

代碼

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


fromcollectionsimportCounter
frommathimportinf


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


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

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

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

print(ans)

時(shí)空復(fù)雜度

時(shí)間復(fù)雜度：O(N)。僅需一次遍歷整個(gè)字符串s。

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

審核編輯：湯梓紅