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

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

题目描述

给你一个字符串 s 。

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

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

请你返回进行 最后 一次操作 之前 的字符串 s。

示例 1：

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

示例 2：

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

提示：

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

解题思路

首先创建一个空对象 map，用于记录字符串中每个字符出现的次数。同时初始化变量 max 为 0，用于记录最大的字符出现次数。

接下来使用一个循环遍历字符串 s，对每个字符进行处理。在循环中，将当前字符 s[i] 作为键，将其在 map 对象中的值加 1，并更新 max 的值为当前字符出现次数和 max 的较大值。

然后，根据 map 对象中的字符出现次数，倒序遍历字符串 s。如果当前字符的出现次数等于 max，则将该字符从 map 对象中删除，并将该字符加到结果字符串 str 的前面。

最后，返回结果字符串 str。

该算法的时间复杂度为 O(n)，其中 n 是字符串 s 的长度。它需要遍历两次字符串，一次用于统计字符出现次数，一次用于构建结果字符串。空间复杂度取决于字符串中不同字符的数量，为 O(k)，其中 k 是字符串中不同字符的数量。

AC代码

/**
 * @param {string} s
 * @return {string}
 */
var lastNonEmptyString = function (s) {
  const map = {};
  let max = 0;
  for (let i = 0; i < s.length; i++) {
    map[s[i]] = (map[s[i]] || 0) + 1;
    max = Math.max(max, map[s[i]]);
  }
  let str = "";
  for (let i = s.length - 1; i >= 0; i--) {
    let k = s[i];
    if (map[k] === max) {
      delete map[k];
      str = k + str;
    }
  }
  return str;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。