Leetcode 3039 - Apply Operations to Make String Empty

題目

Problem#

給你一個字串 s,每次都從中刪除所有第一次出現的字元,問你刪除到最後一步(再刪除一次就變成空字串)時,所刪除的子字串是什麼?

測資限制#

  • $1 \le s \le 5 \cdot 10^5$

想法#

根據個別字元的出現次數去標記,會長得像以下範例:

1
2
3
a a b c b b c a
1 2 1 1 2 3 2 3
^ ^

我們關心的是最大的數字(最後一步驟),也就是 3,掃一遍判斷如果是 3 的話,加到答案中。

AC Code#

  • 時間複雜度: $\mathcal{O}(n)$
  • 空間複雜度: $\mathcal{O}(n)$