※ 引述 《Meaverzt (單推凜寶)》 之銘言：
:
: 題目
:
: 有一個字串s
:
: 對每個index我們都要找左邊跟右邊最近出現過的s[index]把他刪掉
:
: 如果沒有就不用理他
:
: 最後回傳字串的長度
:
: 思路：
:
: 去計算每個字出現過幾遍
:
: 總共會有三種情況
:
: 1.出現少於3遍：沒辦法繼續簡化 答案長度加上出現的次數
:
: 2.出現奇數遍：因為每次簡化長度會減2 所以最後答案長度+1 eg:aaaaa最後會只剩a
:
: 3.出現偶數遍：答案長度+2 eg:aaaa最後會剩aa
:
: 每個字跑完長度加起來就是答案了
:
: Code:
:
: class Solution(object):
: def minimumLength(self, s):
:
: dict={}
: for i in s:
: if i not in dict:
: dict[i]=1
: else:
: dict[i]+=1
: ans=0
: for i in dict:
: if dict[i]<3:
: ans+=dict[i]
: else:
: ans+=2 if dict[i]%2==0 else 1
: return ans
思路:
差不多
奇數能減到剩一個 偶數能減到剩兩個
長度扣掉能扣的就是答案
Python Code:
class Solution:
def minimumLength(self, s: str) -> int:
record = [0] * 26
n = len(s)
for c in s:
record[ord(c) - ord("a")] += 1
for i in range(26):
if record[i] == 0:
continue
if record[i] % 2 == 1:
n -= record[i] - 1
else:
n -= record[i] - 2
return n