Medium

题目描述

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

你必须重复执行以下操作，直到字符串 s 中不再有至少两个连续字符：

  • 删除字符串中最左边的一对相邻字符，这两个字符在字母表中是连续的，可以是任意顺序（例如，‘a’ 和 ‘b’，或 ‘b’ 和 ‘a’）。
  • 将剩余字符向左移动以填补空隙。

返回无法执行更多操作后得到的字符串。

注意： 将字母表视为环形，因此 ‘a’ 和 ‘z’ 是连续的。

示例 1：

输入：s = "abc"
输出："c"
解释：
从字符串中删除 "ab"，剩余字符串为 "c"。
无法执行更多操作。因此，所有可能删除后的结果字符串是 "c"。

示例 2：

输入：s = "adcb"
输出：""
解释：
从字符串中删除 "dc"，剩余字符串为 "ab"。
从字符串中删除 "ab"，剩余字符串为 ""。
无法执行更多操作。因此，所有可能删除后的结果字符串是 ""。

示例 3：

输入：s = "zadb"
输出："db"
解释：
从字符串中删除 "za"，剩余字符串为 "db"。
无法执行更多操作。因此，所有可能删除后的结果字符串是 "db"。

约束条件：

  • 1 <= s.length <= 10^5
  • s 仅由小写英文字母组成。

解题思路

这道题的关键是要理解删除操作的规则：删除相邻的两个字符，它们在字母表中必须是连续的（考虑环形）。

解题思路

使用栈来模拟删除过程是最直观的方法：

  1. 栈的使用：从左到右遍历字符串，使用栈来维护当前剩余的字符。

  2. 判断连续性：对于当前字符 c 和栈顶字符 top，判断它们是否在字母表中连续：

    • 正常连续：|c - top| == 1
    • 环形连续：一个是 ‘a’ 另一个是 ‘z’（即 |c - top| == 25）

  3. 操作逻辑：

    • 如果栈为空，直接将当前字符入栈
    • 如果当前字符与栈顶字符连续，弹出栈顶（相当于删除这对字符）
    • 否则，将当前字符入栈

  4. 结果构造：遍历完成后，栈中剩余的字符就是最终结果。

这种方法能够正确处理删除操作的"最左边优先"规则，因为我们是从左到右处理的，每次遇到可以删除的情况就立即删除。

时间复杂度为 O(n)，每个字符最多入栈出栈一次。空间复杂度为 O(n)，栈的最大容量。

代码实现

class Solution {
public:
    string resultingString(string s) {
        string stack;
        
        for (char c : s) {
            if (!stack.empty() && isConsecutive(stack.back(), c)) {
                stack.pop_back();
            } else {
                stack.push_back(c);
            }
        }
        
        return stack;
    }
    
private:
    bool isConsecutive(char a, char b) {
        int diff = abs(a - b);
        return diff == 1 || diff == 25;
    }
};

class Solution:
    def resultingString(self, s: str) -> str:
        stack = []
        
        for c in s:
            if stack and self.is_consecutive(stack[-1], c):
                stack.pop()
            else:
                stack.append(c)
        
        return ''.join(stack)
    
    def is_consecutive(self, a: str, b: str) -> bool:
        diff = abs(ord(a) - ord(b))
        return diff == 1 or diff == 25

public class Solution {
    public string ResultingString(string s) {
        var stack = new List<char>();
        
        foreach (char c in s) {
            if (stack.Count > 0 && IsConsecutive(stack[stack.Count - 1], c)) {
                stack.RemoveAt(stack.Count - 1);
            } else {
                stack.Add(c);
            }
        }
        
        return new string(stack.ToArray());
    }
    
    private bool IsConsecutive(char a, char b) {
        int diff = Math.Abs(a - b);
        return diff == 1 || diff == 25;
    }
}

var resultingString = function(s) {
    let stack = [];
    
    for (let char of s) {
        if (stack.length > 0) {
            let top = stack[stack.length - 1];
            let diff = Math.abs(char.charCodeAt(0) - top.charCodeAt(0));
            if (diff === 1 || diff === 25) {
                stack.pop();
            } else {
                stack.push(char);
            }
        } else {
            stack.push(char);
        }
    }
    
    return stack.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n)每个字符最多入栈出栈一次，n 为字符串长度
空间复杂度O(n)栈的空间开销，最坏情况下存储所有字符