Medium

题目描述

给你一个字符串 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 * 10^5
  • s 仅包含小写英文字母。

提示：

  • 在最后一次操作之前，只有原始字符串中出现次数最多的字符会保留。
  • 只保留每个出现次数最多的字符的最后一次出现。

解题思路

解题思路：

这道题的关键观察是：在每轮操作中，我们按字母顺序删除每个字符的第一次出现。最终剩下的字符都是那些在原字符串中出现次数最多的字符，并且是它们的最后一次出现。

具体分析：

  1. 首先统计每个字符的出现次数，找到最大出现次数
  2. 在最后的非空字符串中，只会包含出现次数等于最大次数的字符
  3. 对于这些字符，只有它们的最后一次出现会被保留
  4. 我们从右到左遍历原字符串，记录每个最频繁字符的最后出现位置
  5. 按照这些位置的相对顺序构建最终结果

算法步骤：

  1. 统计所有字符的频次，找到最大频次
  2. 从右往左遍历字符串，对于频次等于最大频次的字符，记录其位置（只记录第一次遇到的，即原字符串中的最后一次出现）
  3. 按照记录的位置顺序输出字符

这个方法的时间复杂度是O(n)，空间复杂度是O(1)（因为只有26个小写字母）。

代码实现

class Solution {
public:
    string lastNonEmptyString(string s) {
        vector<int> count(26, 0);
        
        // 统计每个字符的出现次数
        for (char c : s) {
            count[c - 'a']++;
        }
        
        // 找到最大出现次数
        int maxCount = *max_element(count.begin(), count.end());
        
        string result;
        vector<bool> used(26, false);
        
        // 从右往左遍历，找到每个最频繁字符的最后出现位置
        for (int i = s.length() - 1; i >= 0; i--) {
            int idx = s[i] - 'a';
            if (count[idx] == maxCount && !used[idx]) {
                result = s[i] + result;
                used[idx] = true;
            }
        }
        
        return result;
    }
};

class Solution:
    def lastNonEmptyString(self, s: str) -> str:
        from collections import Counter
        
        # 统计每个字符的出现次数
        count = Counter(s)
        max_count = max(count.values())
        
        result = []
        used = set()
        
        # 从右往左遍历，找到每个最频繁字符的最后出现位置
        for i in range(len(s) - 1, -1, -1):
            char = s[i]
            if count[char] == max_count and char not in used:
                result.append(char)
                used.add(char)
        
        # 反转结果，因为我们是从右往左添加的
        return ''.join(reversed(result))

public class Solution {
    public string LastNonEmptyString(string s) {
        int[] count = new int[26];
        
        // 统计每个字符的出现次数
        foreach (char c in s) {
            count[c - 'a']++;
        }
        
        // 找到最大出现次数
        int maxCount = count.Max();
        
        StringBuilder result = new StringBuilder();
        bool[] used = new bool[26];
        
        // 从右往左遍历，找到每个最频繁字符的最后出现位置
        for (int i = s.Length - 1; i >= 0; i--) {
            int idx = s[i] - 'a';
            if (count[idx] == maxCount && !used[idx]) {
                result.Insert(0, s[i]);
                used[idx] = true;
            }
        }
        
        return result.ToString();
    }
}

var lastNonEmptyString = function(s) {
    const count = new Array(26).fill(0);
    
    // 统计每个字符的出现次数
    for (const char of s) {
        count[char.charCodeAt(0) - 97]++;
    }
    
    // 找到最大出现次数
    const maxCount = Math.max(...count);
    
    let result = '';
    const used = new Set();
    
    // 从右往左遍历，找到每个最频繁字符的最后出现位置
    for (let i = s.length - 1; i >= 0; i--) {
        const char = s[i];
        const idx = char.charCodeAt(0) - 97;
        if (count[idx]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(1)

其中 n 是字符串 s 的长度。空间复杂度为 O(1) 是因为我们只使用了固定大小的数组来存储 26 个字母的信息。