ETH官方钱包

前往
大廳
主題

LeetCode - 2716. Minimize String Length 解題心得

Not In My Back Yard | 2024-08-21 12:00:13 | 巴幣 2 | 人氣 42

題目連結:


題目意譯:
給定一個字串 s。你有以下兩種操作:
    選擇字串中一個索引值 i,並令 c 為索引值 i 上的字元。刪除位於 i 左側的另一個且最靠近原本字元的 c(如果存在)、
    選擇字串中一個索引值 i,並令 c 為索引值 i 上的字元。刪除位於 i 右側的另一個且最靠近原本字元的 c(如果存在)。

你的任務是藉由執行以上操作零次或多次來最小化 s 的長度。

回傳一個整數代表著最小化後的字串長度。

限制:
1 ≦ s.length ≦ 100
s 只包含小寫英文字母。



範例測資:
範例 1:
輸入: s = "aaabc"
輸出: 3
解釋:
1. 操作 2:我們選擇 i = 1 所以 c 為 'a',則我們將移除 s[2] 因為其為最靠近且位於右側 s[1] 的字元 'a'。
經過這個之後,s 會變成 "aabc"。
2. 操作 1:我們選擇 i = 1 所以 c 為 'a',則我們將移除 s[0] 因為其為最靠近且位於左側 s[1] 的字元 'a'。
經過這個之後,s 會變成 "abc"。

範例 2:
輸入: s = "cbbd"
輸出: 3
解釋:
1. 操作 1:我們選擇 i = 2 所以 c 為 'b',則我們將移除 s[1] 因為其為最靠近且位於左側 s[1] 的字元 'b'。
經過這個之後,s 會變成 "cbd"。

範例 3:
輸入: s = "baadccab"
輸出: 4
解釋:
1. 操作 1:我們選擇 i = 6 所以 c 為 'a',則我們將移除 s[2] 因為其為最靠近且位於左側 s[6] 的字元 'a'。
經過這個之後,s 會變成 "badccab"。
2. 操作 2:我們選擇 i = 0 所以 c 為 'b',則我們將移除 s[6] 因為其為最靠近且位於右側 s[10 的字元 'b'。
經過這個之後,s 會變成 "badcca"。
3. 操作 2:我們選擇 i = 3 所以 c 為 'c',則我們將移除 s[4] 因為其為最靠近且位於右側 s[3] 的字元 'c'。
經過這個之後,s 會變成 "badca"。
4. 操作 1:我們選擇 i = 4 所以 c 為 'a',則我們將移除 s[1] 因為其為最靠近且位於左側 s[4] 的字元 'a'。
經過這個之後,s 會變成 "bdca"。


解題思維:
可以看到對於每一種字元,我們可以一直選最先出現的那一個然後刪掉後面才出現的該種字元。因此每一種字元都一定可以消到只剩一個。

因此所求即為 s 中的字元種類數。




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

創作回應

更多創作