4019. 合并靠近字符 II 🔒

题目描述

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

如果两个相同的字符 s[i] 和 s[j] 满足 0 <= i < j < s.length 且 j - i <= k，则认为它们是靠近的。所有下标均指当前字符串中的下标。

重复执行以下操作，直到不存在靠近字符对：

在所有相邻字符对 (i, j) 中，选择 i 最小的那一对。如果存在多个具有相同 i 的相邻字符对，则选择 j 最小的那一对。
将右侧字符合并到左侧字符中，即从 s 中删除 s[j]。字符 s[i] 保持不变，其余字符重新编号。

返回执行所有可能的合并操作后得到的字符串。

示例 1：

输入： s = "abca", k = 3

输出： "abc"

解释：

下标为 0 和 3 的字符 'a' 是相邻的，因为 3 - 0 = 3 <= k。
删除右侧的 'a'，得到 s = "abc"。
不存在相邻字符对，因此不再进行合并。

示例 2：

输入： s = "aabca", k = 2

输出： "abca"

解释：

下标为 0 和 1 的字符 'a' 是相邻的，因为 1 - 0 = 1 <= k。
删除右侧的 'a'，得到 s = "abca"。
剩余的两个 'a' 位于下标 0 和 3。由于 3 - 0 = 3 > k，不存在相邻字符对。

示例 3：

输入： s = "yybyzybz", k = 2

输出： "ybzybz"

解释：

下标为 0 和 1 的字符 'y' 是相邻的，因为 1 - 0 = 1 <= k。这对字符的左侧下标是所有相邻字符对中最小的。
删除右侧的 'y'，得到 s = "ybyzybz"。
此时下标为 0 和 2 的字符 'y' 是相邻的，因为 2 - 0 = 2 <= k。
删除右侧的 'y'，得到 s = "ybzybz"。
不存在相邻字符对，因此不再进行合并。

提示：

1 <= s.length <= 5 * 10⁵
1 <= k <= s.length
s 由小写英文字母组成。

解法

方法一：哈希表

我们使用一个哈希表 \(\textit{last}\) 记录每个字符在答案字符串中上一次出现的位置。从左到右遍历 \(s\) 的每个字符：设当前答案长度为 \(\textit{cur}\)，若该字符已出现过，且 \(\textit{cur}\) 与其上一次出现位置之差不超过 \(k\)，则跳过该字符；否则将该字符加入答案，并更新哈希表中的位置。

按题意每次合并总是删除右侧字符，因此答案中每个字符的位置即为当前字符串中的下标。上述贪心过程与反复执行合并操作得到的结果等价。

Python3JavaC++GoTypeScript

class Solution:
    def mergeCharacters(self, s: str, k: int) -> str:
        last = {}
        ans = []
        for c in s:
            cur = len(ans)
            if c in last and cur - last[c] <= k:
                continue
            ans.append(c)
            last[c] = cur
        return ''.join(ans)

class Solution {
    public String mergeCharacters(String s, int k) {
        Map<Character, Integer> last = new HashMap<>();
        StringBuilder ans = new StringBuilder();
        for (char c : s.toCharArray()) {
            int cur = ans.length();
            if (last.containsKey(c) && cur - last.get(c) <= k) {
                continue;
            }
            ans.append(c);
            last.put(c, cur);
        }
        return ans.toString();
    }
}

class Solution {
public:
    string mergeCharacters(string s, int k) {
        unordered_map<char, int> last;
        string ans;
        for (char c : s) {
            int cur = ans.size();
            if (last.count(c) && cur - last[c] <= k) {
                continue;
            }
            ans += c;
            last[c] = cur;
        }
        return ans;
    }
};

func mergeCharacters(s string, k int) string {
    last := make(map[byte]int)
    var ans []byte
    for i := 0; i < len(s); i++ {
        c := s[i]
        cur := len(ans)
        if lastIdx, ok := last[c]; ok && cur-lastIdx <= k {
            continue
        }
        ans = append(ans, c)
        last[c] = cur
    }
    return string(ans)
}

function mergeCharacters(s: string, k: number): string {
    const last = new Map<string, number>();
    const ans: string[] = [];
    for (const c of s) {
        const cur = ans.length;
        if (last.has(c) && cur - last.get(c)! <= k) {
            continue;
        }
        ans.push(c);
        last.set(c, cur);
    }
    return ans.join('');
}

4019. 合并靠近字符 II 🔒

题目描述

解法

方法一：哈希表

评论