Problem#
給你一個字串 s
,每次都從中刪除所有第一次出現的字元,問你刪除到最後一步(再刪除一次就變成空字串)時,所刪除的子字串是什麼?
測資限制#
- $1 \le s \le 5 \cdot 10^5$
想法#
根據個別字元的出現次數去標記,會長得像以下範例:
1 | a a b c b b c a |
我們關心的是最大的數字(最後一步驟),也就是 3
,掃一遍判斷如果是 3
的話,加到答案中。
AC Code#
- 時間複雜度: $\mathcal{O}(n)$
- 空間複雜度: $\mathcal{O}(n)$