ETH官方钱包

前往
大廳
主題

LeetCode - 2516. Take K of Each Character From Left and Right 解題心得

Not In My Back Yard | 2023-11-15 12:00:04 | 巴幣 0 | 人氣 118

題目連結:


題目意譯:
你被給定一個由字元 'a' 、 'b' 和 'c' 所組成的字串 s 以及一非負整數 k。在每一分鐘,你可以拿走 s 現在最左邊的字元或是最右邊的字元。

回傳你至少拿走每一種各自 k 個字元最少所需的分鐘數。如果沒辦法拿走每一種各自 k 個字元則回傳 -1。

限制:
1 ≦ s.length ≦ 10 ^ 5
s 只由字母 'a' 、 'b' 和 'c' 所組成。
0 ≦ k ≦ s.length



範例測資:
範例 1:
輸入: s = "aabaaaacaabc", k = 2
輸出: 8
解釋:
從 s 的左側拿走三個字元。你現在有兩個 'a' 和一個 'b'。
從 s 的右側拿走五個字元。你現在有四個 'a' 、兩個 'b' 和兩個 'c'。
總計所需分鐘數為 3 + 5 = 8。
可以證明 8 是最少所需分鐘數。

範例 2:
輸入: s = "a", k = 1
輸出: -1
解釋: 沒辦法拿走一個 'b' 或 'c',所以回傳 -1。


解題思維:
首先,如果 k == 0,則當然什麼字元都不用拿。因此直接回傳 0 即可;再來如果拿走整個字串都還不夠的話(也就是說 'a' 、 'b' 或是 'c' 其中一者的數量 < k),就直接回傳 0 即可。

而剩下的情況則需要交由滑動視窗(Sliding Window)來解決(如這題),而因為我們一次是從左右拿字元,因此這個「視窗」將很有可能會同時橫跨左邊界和右邊界,也就是說看起來會有兩個「視窗」:一個靠左、一個靠右。但實際上兩者是同一個。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作