前往
大廳
主題

LeetCode - 2182. Construct String With Repeat Limit 解題心得

Not In My Back Yard | 2022-10-02 12:00:09 | 巴幣 0 | 人氣 164

題目連結:


題目意譯:
你被給定一字串 s 以及一整數 repeatLimit。請使用 s 中的字元來建構出一個新的字串 repeatLimitedString,使得沒有字母連續出現多於 repeatLimit 次。你不一定要使用掉 s 中所有的字元。

回傳所有可能的 repeatLimitedString 中字典序最大者。

一字串 a 之字典序大於另一字串 b,代表著在 a 和 b 第一個不同的位置上,字串 a 有著一字母在字母表上出現得比 b 對應位置的字母還要來得晚。如果前 min(a.length, b.length) 個字母都相同,則較長的字串之字典序較大。

限制:
1 ≦ repeatLimit ≦ s.length ≦ 10 ^ 5
s 由小寫英文字母組成。



範例測資:
範例 1:
輸入: s = "cczazcc", repeatLimit = 3
輸出: "zzcccac"
解釋: 我們使用 s 中的所有字元來建造出 repeatLimitedString 字串 "zzcccac"。
字母 'a' 最多連續出現 1 次。
字母 'c' 最多連續出現 3 次。
字母 'z' 最多連續出現 1 次。
因此沒有字母連續出現多於 repeatLimit 次,因此該字串為一個合法的 repeatLimitedString。
該字串是所有可能的 repeatLimitedString 中字典序最大的,因此我們回傳 "zzcccac"。
注意到字串 "zzcccca" 的字典序更大,但是字母 'c' 連續出現多於 3 次,因此其並不是一個合法的 repeatLimitedString。

範例 2:
輸入: s = "aababab", repeatLimit = 2
輸出: "bbabaa"
解釋: 我們只使用 s 中的部分字元來建造出 repeatLimitedString 字串 "zzcccac"。
字母 'a' 最多連續出現 2 次。
字母 'b' 最多連續出現 2 次。
因此沒有字母連續出現多於 repeatLimit 次,因此該字串為一個合法的 repeatLimitedString。
該字串是所有可能的 repeatLimitedString 中字典序最大的,因此我們回傳 "bbabaa"。
注意到字串 "bbabaaa" 的字典序更大,但是字母 'a' 連續出現多於 2 次,因此其並不是一個合法的 repeatLimitedString。


解題思維:
其實作法很簡單——先掃過一次 s 並統計每一種字母出現的次數。然後挑字典序最大的字母放到新的字串之尾端即可。

至於連續出現的限制只需要檢查當前建造出來的新字串之尾端字母出現了幾次(假設為 C),如果 C 已經到了 repeatLimit 次,則就算有再多的同樣字母也應該要換別的字母(即下一個最大的字母,如果存在的話)。

而如果不存在可以挑的字母來加到新字串中(例如說 s 的字母都用光了,或是沒有下一個最大的字母可以加等等),就表示現在造出來的字串即是字典序最大的 repeatLimitedString。




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

創作回應

更多創作