題目連結:
題目意譯:
給定一個字串 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 中的字元種類數。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。