Problem#
令字母出現次數不重複的字串叫做好字串，問你今天給你一個字串，能夠最小刪除多少，使得字串變成好字串？
測資限制#
- $1 \le n \le 10^5$
想法#
統計每個字母(c)出現的次數 m[c]，從大排到小，如果 $i$ 出現過了，則減一，檢查 $i-1$ 是否出現過，以此類推，在過程中統計減去的數值。
- 時間複雜度: $\mathcal{O}(n\log{n}+k^2)$
- $k$ = 最大的重複次數
- 最差的狀況：全部都一樣，第一個不用減，第二個要減一，第三個要減二，⋯⋯ 以此類推。總和：$\frac{(0+k-1)k}{2} = \frac{k^2-k}{2}$ -> $O(n)$
- 空間複雜度: $\mathcal{O}(n)$
AC Code#
心得#
寫完才發現自己以前寫過一次