3561. 移除相邻字符

题目描述

给你一个由小写英文字母组成的字符串 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⁵
s 仅由小写英文字母组成。

解法

方法一：栈

我们可以使用栈来模拟移除相邻字符的过程。遍历字符串中的每个字符，如果栈顶字符与当前字符是连续的（即它们的 ASCII 值差为 1 或 25），则将栈顶字符弹出；否则，将当前字符压入栈中。最后，栈中的字符就是无法再移除的结果，我们将栈中的字符连接成字符串并返回。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)，其中 \(n\) 是字符串的长度。

Python3JavaC++GoTypeScript

class Solution:
    def resultingString(self, s: str) -> str:
        stk = []
        for c in s:
            if stk and abs(ord(c) - ord(stk[-1])) in (1, 25):
                stk.pop()
            else:
                stk.append(c)
        return "".join(stk)

class Solution {
    public String resultingString(String s) {
        StringBuilder stk = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (stk.length() > 0 && isContiguous(stk.charAt(stk.length() - 1), c)) {
                stk.deleteCharAt(stk.length() - 1);
            } else {
                stk.append(c);
            }
        }
        return stk.toString();
    }

    private boolean isContiguous(char a, char b) {
        int t = Math.abs(a - b);
        return t == 1 || t == 25;
    }
}

class Solution {
public:
    string resultingString(string s) {
        string stk;
        for (char c : s) {
            if (stk.size() && (abs(stk.back() - c) == 1 || abs(stk.back() - c) == 25)) {
                stk.pop_back();
            } else {
                stk.push_back(c);
            }
        }
        return stk;
    }
};

func resultingString(s string) string {
    isContiguous := func(a, b rune) bool {
        x := abs(int(a - b))
        return x == 1 || x == 25
    }
    stk := []rune{}
    for _, c := range s {
        if len(stk) > 0 && isContiguous(stk[len(stk)-1], c) {
            stk = stk[:len(stk)-1]
        } else {
            stk = append(stk, c)
        }
    }
    return string(stk)
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

function resultingString(s: string): string {
    const stk: string[] = [];
    const isContiguous = (a: string, b: string): boolean => {
        const x = Math.abs(a.charCodeAt(0) - b.charCodeAt(0));
        return x === 1 || x === 25;
    };
    for (const c of s) {
        if (stk.length && isContiguous(stk.at(-1)!, c)) {
            stk.pop();
        } else {
            stk.push(c);
        }
    }
    return stk.join('');
}

3561. 移除相邻字符

题目描述

解法

方法一：栈

评论