Question

3039. 进行操作使字符串为空

English Version

题目描述

给你一个字符串 s 。

请你进行以下操作直到 s 为 空 ：

• 每次操作 依次 遍历 'a' 到 'z'，如果当前字符出现在 s 中，那么删除出现位置 最早 的该字符（如果存在的话）。

例如，最初 s = "aabcbbca"。我们执行下述操作：

• 移除下划线的字符  s = "aabcbbca"。结果字符串为 s = "abbca"。
• 移除下划线的字符  s = "abbca"。结果字符串为 s = "ba"。
• 移除下划线的字符  s = "ba"。结果字符串为 s = ""。

请你返回进行 最后 一次操作 之前 的字符串_ _s_ _。在上面的例子中，答案是 "ba"。

 

示例 1：

输入：s = "aabcbbca"
输出："ba"
解释：已经在题目描述中解释。

示例 2：

输入：s = "abcd"
输出："abcd"
解释：我们进行以下操作：
- 删除 s = "_abcd_" 中加粗加斜字符，得到字符串 s = "" 。
进行最后一次操作之前的字符串为 "abcd" 。

 

提示：

• 1 <= s.length <= 5 * 105
• s 只包含小写英文字母。

解法

方法一：哈希表或数组

我们用一个哈希表或数组 $cnt$ 记录字符串 $s$ 中每个字符的出现次数，用一个哈希表或数组 $last$ 记录字符串 $s$ 中每个字符最后一次出现的位置。字符串 $s$ 中出现次数最多的字符的出现次数记为 $mx$。

然后我们遍历字符串 $s$，如果当前字符的出现次数等于 $mx$ 且当前字符所在位置等于该字符最后一次出现的位置，那么我们将当前字符加入答案中。

遍历结束后，返回答案即可。

时间复杂度 $O(n)$，空间复杂度 $O(|\Sigma|)$，其中 $n$ 是字符串 $s$ 的长度，而 $\Sigma$ 是字符集，本题中 $\Sigma$ 为小写英文字母。

class Solution:
  def lastNonEmptyString(self, s: str) -> str:
    cnt = Counter(s)
    mx = cnt.most_common(1)[0][1]
    last = {c: i for i, c in enumerate(s)}
    return "".join(c for i, c in enumerate(s) if cnt[c] == mx and last[c] == i)

class Solution {
  public String lastNonEmptyString(String s) {
    int[] cnt = new int[26];
    int[] last = new int[26];
    int n = s.length();
    int mx = 0;
    for (int i = 0; i < n; ++i) {
      int c = s.charAt(i) - 'a';
      mx = Math.max(mx, ++cnt[c]);
      last[c] = i;
    }
    StringBuilder ans = new StringBuilder();
    for (int i = 0; i < n; ++i) {
      int c = s.charAt(i) - 'a';
      if (cnt[c] == mx && last[c] == i) {
        ans.append(s.charAt(i));
      }
    }
    return ans.toString();
  }
}

class Solution {
public:
  string lastNonEmptyString(string s) {
    int cnt[26]{};
    int last[26]{};
    int n = s.size();
    int mx = 0;
    for (int i = 0; i < n; ++i) {
      int c = s[i] - 'a';
      mx = max(mx, ++cnt[c]);
      last[c] = i;
    }
    string ans;
    for (int i = 0; i < n; ++i) {
      int c = s[i] - 'a';
      if (cnt[c] == mx && last[c] == i) {
        ans.push_back(s[i]);
      }
    }
    return ans;
  }
};

func lastNonEmptyString(s string) string {
  cnt := [26]int{}
  last := [26]int{}
  mx := 0
  for i, c := range s {
    c -= 'a'
    cnt[c]++
    last[c] = i
    mx = max(mx, cnt[c])
  }
  ans := []rune{}
  for i, c := range s {
    if cnt[c-'a'] == mx && last[c-'a'] == i {
      ans = append(ans, c)
    }
  }
  return string(ans)
}

function lastNonEmptyString(s: string): string {
  const cnt: number[] = Array(26).fill(0);
  const last: number[] = Array(26).fill(0);
  const n = s.length;
  let mx = 0;
  for (let i = 0; i < n; ++i) {
    const c = s.charCodeAt(i) - 97;
    mx = Math.max(mx, ++cnt[c]);
    last[c] = i;
  }
  const ans: string[] = [];
  for (let i = 0; i < n; ++i) {
    const c = s.charCodeAt(i) - 97;
    if (cnt[c] === mx && last[c] === i) {
      ans.push(String.fromCharCode(c + 97));
    }
  }
  return ans.join('');
}