Hard

题目描述

给你一个由小写英文字母组成的字符串 s。

你可以执行以下操作任意次（可能是 0 次）：

  • 选择当前字符串 s 中出现至少两次的任意字母，并删除其中任意一个出现位置。

返回通过这种方式能够形成的字典序最小的结果字符串。

示例 1：

输入：s = "aaccb"
输出："aacb"
解释：
我们可以形成字符串 "acb"、"aacb"、"accb" 和 "aaccb"。"aacb" 是字典序最小的。
例如，我们可以通过选择 'c' 并删除其第一个出现位置来获得 "aacb"。

示例 2：

输入：s = "z"
输出："z"
解释：
我们无法执行任何操作。我们能形成的唯一字符串是 "z"。

约束：

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

提示：

  • 贪心求解。
  • 每个不同的字母在最终字符串中必须至少出现一次。
  • 对于每个字母，维护其位置的双端队列。
  • 在每一步中，尝试从 ‘a’ 到 ‘z’ 的字母，并选择最早位置在安全窗口内的最小字母。
  • 如果选择某个出现位置会使其他字母无法保留，则不要选择它。
  • 标记位置为已使用并重复，始终最小化下一个选择的字符。

解题思路

这是一个贪心算法问题，核心思想是在保证每个字符至少出现一次的前提下，尽可能选择字典序较小的字符。

解题思路：

  1. 预处理阶段：统计每个字符的出现次数和位置，为每个字符创建位置队列。

  2. 贪心选择：从左到右构建结果字符串，每次都尝试选择当前能选择的最小字符：

    • 按字母顺序 ‘a’ 到 ‘z’ 遍历
    • 对于每个字符，检查是否可以安全选择其最早的未使用位置
    • “安全"的定义是：选择这个位置后，剩余的字符串中仍能保证所有必需字符至少出现一次

  3. 安全性检查：对于位置 pos，需要确保在 pos 之后的字符串中，所有剩余的必需字符都至少有一个出现位置。

  4. 状态更新：选择一个字符后，更新该字符的剩余次数，如果次数变为1，则该字符变为必需字符（不能再删除）。

这种方法确保我们总是优先选择字典序最小的安全字符，从而得到全局最优解。

时间复杂度主要来自于对每个位置的安全性检查，空间复杂度用于存储字符位置信息。

代码实现

class Solution {
public:
    string lexSmallestAfterDeletion(string s) {
        int n = s.length();
        vector<vector<int>> pos(26);
        vector<int> count(26, 0);
        
        // 记录每个字符的位置和出现次数
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'a';
            pos[c].push_back(i);
            count[c]++;
        }
        
        string result;
        vector<bool> used(n, false);
        
        while (result.length() < n) {
            bool found = false;
            
            // 尝试从 'a' 到 'z'
            for (int c = 0; c < 26; c++) {
                if (pos[c].empty()) continue;
                
                // 找到第一个未使用的位置
                int earliestPos = -1;
                for (int p : pos[c]) {
                    if (!used[p]) {
                        earliestPos = p;
                        break;
                    }
                }
                
                if (earliestPos == -1) continue;
                
                // 检查选择这个位置是否安全
                bool safe = true;
                for (int other = 0; other < 26; other++) {
                    if (other == c || pos[other].empty()) continue;
                    
                    // 计算这个字符在 earliestPos 之后还有多少个未使用的位置
                    int remaining = 0;
                    for (int p : pos[other]) {
                        if (p > earliestPos && !used[p]) {
                            remaining++;
                        }
                    }
                    
                    // 如果这个字符只剩一个位置且都在 earliestPos 之前，则不安全
                    if (count[other] == 1 && remaining == 0) {
                        safe = false;
                        break;
                    }
                }
                
                if (safe) {
                    result += (char)('a' + c);
                    used[earliestPos] = true;
                    count[c]--;
                    found = true;
                    break;
                }
            }
            
            if (!found) break;
        }
        
        return result;
    }
};

class Solution:
    def lexSmallestAfterDeletion(self, s: str) -> str:
        n = len(s)
        pos = [[] for _ in range(26)]
        count = [0] * 26
        
        # 记录每个字符的位置和出现次数
        for i, char in enumerate(s):
            c = ord(char) - ord('a')
            pos[c].append(i)
            count[c] += 1
        
        result = []
        used = [False] * n
        
        while len(result) < n:
            found = False
            
            # 尝试从 'a' 到 'z'
            for c in range(26):
                if not pos[c]:
                    continue
                
                # 找到第一个未使用的位置
                earliest_pos = -1
                for p in pos[c]:
                    if not used[p]:
                        earliest_pos = p
                        break
                
                if earliest_pos == -1:
                    continue
                
                # 检查选择这个位置是否安全
                safe = True
                for other in range(26):
                    if other == c or not pos[other]:
                        continue
                    
                    # 计算这个字符在 earliest_pos 之后还有多少个未使用的位置
                    remaining = sum(1 for p in pos[other] if p > earliest_pos and not used[p])
                    
                    # 如果这个字符只剩一个位置且都在 earliest_pos 之前，则不安全
                    if count[other] == 1 and remaining == 0:
                        safe = False
                        break
                
                if safe:
                    result.append(chr(ord('a') + c))
                    used[earliest_pos] = True
                    count[c] -= 1
                    found = True
                    break
            
            if not found:
                break
        
        return ''.join(result)

public class Solution {
    public string LexSmallestAfterDeletion(string s) {
        int n = s.Length;
        List<int>[] pos = new List<int>[26];
        int[] count = new int[26];
        
        // 初始化位置列表
        for (int i = 0; i < 26; i++) {
            pos[i] = new List<int>();
        }
        
        // 记录每个字符的位置和出现次数
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'a';
            pos[c].Add(i);
            count[c]++;
        }
        
        StringBuilder result = new StringBuilder();
        bool[] used = new bool[n];
        
        while (result.Length < n) {
            bool found = false;
            
            // 尝试从 'a' 到 'z'
            for (int c = 0; c < 26; c++) {
                if (pos[c].Count == 0) continue;
                
                // 找到第一个未使用的位置
                int earliestPos = -1;
                foreach (int p in pos[c]) {
                    if (!used[p]) {
                        earliestPos = p;
                        break;
                    }
                }
                
                if (earliestPos == -1) continue;
                
                // 检查选择这个位置是否安全
                bool safe = true;
                for (int other = 0; other < 26; other++) {
                    if (other == c || pos[other].Count == 0) continue;
                    
                    // 计算这个字符在 earliestPos 之后还有多少个未使用的位置
                    int remaining = 0;
                    foreach (int p in pos[other]) {
                        if (p > earliestPos && !used[p]) {
                            remaining++;
                        }
                    }
                    
                    // 如果这个字符只剩一个位置且都在 earliestPos 之前，则不安全
                    if (count[other] == 1 && remaining == 0) {
                        safe = false;
                        break;
                    }
                }
                
                if (safe) {
                    result.Append((char)('a' + c));
                    used[earliestPos] = true;
                    count[c]--;
                    found = true;
                    break;
                }
            }
            
            if (!found) break;
        }
        
        return result.ToString();
    }
}

var lexSmallestAfterDeletion = function(s) {
    const count = new Array(26).fill(0);
    for (let char of s) {
        count[char.charCodeAt(0) - 97]++;
    }
    
    const result = [];
    const used = new Array(26).fill(0);
    
    for (let char of s) {
        const idx = char.charCodeAt(0) - 97;
        count[idx]--;
        
        if (used[idx] > 0) continue;
        
        while (result.length > 0 && 
               result[result.length - 1] > char && 
               count[result[result.length - 1].charCodeAt(0) - 97] > 0) {
            const removed = result.pop();
            used[removed.charCodeAt(0) - 97]--;
        }
        
        result.push(char);
        used[idx]++;
    }
    
    return result.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n² × 26) = O(n²)，其中 n 是字符串长度。对于每个位置，我们需要检查所有26个字符的安全性
空间复杂度O(n)，用于存储字符位置信息、使用标记数组和结果字符串

相关题目