Medium

题目描述

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

当前字符串 s 中的两个相同字符如果它们的索引距离不超过 k，则认为它们是相近的。

当两个字符相近时，右边的字符会合并到左边的字符中。合并一次只进行一个操作，每次合并后字符串会更新，直到不能再进行合并为止。

返回执行所有可能合并后的结果字符串。

注意：如果可以进行多个合并，总是选择左索引最小的配对进行合并。如果多个配对具有相同的最小左索引，则选择右索引最小的配对。

示例 1：

输入：s = "abca", k = 3
输出："abc"
解释：
索引 i = 0 和 i = 3 处的字符 'a' 相近，因为 3 - 0 = 3 <= k。
将它们合并到左边的 'a'，s = "abc"。
没有其他相同字符相近，所以不再进行合并。

示例 2：

输入：s = "aabca", k = 2
输出："abca"
解释：
索引 i = 0 和 i = 1 处的字符 'a' 相近，因为 1 - 0 = 1 <= k。
将它们合并到左边的 'a'，s = "abca"。
现在剩余的 'a' 字符在索引 i = 0 和 i = 3 处不相近，因为 k < 3，所以不再进行合并。

示例 3：

输入：s = "yybyzybz", k = 2
输出："ybzybz"
解释：
索引 i = 0 和 i = 1 处的字符 'y' 相近，因为 1 - 0 = 1 <= k。
将它们合并到左边的 'y'，s = "ybyzybz"。
现在索引 i = 0 和 i = 2 处的字符 'y' 相近，因为 2 - 0 = 2 <= k。
将它们合并到左边的 'y'，s = "ybzybz"。
没有其他相同字符相近，所以不再进行合并。

提示：

  • 1 <= s.length <= 100
  • 1 <= k <= s.length
  • s 由小写英文字母组成

解题思路

这道题需要我们模拟字符合并的过程。核心思路是：

  1. 寻找可合并的字符对：遍历字符串，找到距离不超过k的相同字符对
  2. 选择合并策略：按题目要求，优先选择左索引最小的配对，如果左索引相同则选择右索引最小的配对
  3. 执行合并操作：将右边的字符合并到左边，即删除右边的字符
  4. 重复直到无法合并：每次合并后字符串会发生变化，需要重新寻找可合并的字符对

算法步骤：

  • 使用一个布尔标志来控制循环，当没有发生合并时退出
  • 在每轮循环中，遍历所有字符对 (i, j)，其中 i < j 且 j - i <= k
  • 找到字符相同且距离满足条件的最优配对（左索引最小，左索引相同时右索引最小）
  • 执行合并操作后重新开始寻找

这种方法虽然时间复杂度较高，但由于字符串长度限制在100以内，完全可以接受。

推荐解法： 直接模拟法，代码简洁易懂，符合题目要求。

代码实现

class Solution {
public:
    string mergeCharacters(string s, int k) {
        bool merged = true;
        while (merged) {
            merged = false;
            int bestLeft = -1, bestRight = -1;
            
            // 找到最优的合并配对
            for (int i = 0; i < s.length(); i++) {
                for (int j = i + 1; j < s.length() && j - i <= k; j++) {
                    if (s[i] == s[j]) {
                        if (bestLeft == -1 || i < bestLeft || (i == bestLeft && j < bestRight)) {
                            bestLeft = i;
                            bestRight = j;
                        }
                    }
                }
            }
            
            // 如果找到可合并的配对，执行合并
            if (bestLeft != -1) {
                s.erase(bestRight, 1);
                merged = true;
            }
        }
        return s;
    }
};

class Solution:
    def mergeCharacters(self, s: str, k: int) -> str:
        s = list(s)  # 转为列表便于操作
        merged = True
        
        while merged:
            merged = False
            best_left, best_right = -1, -1
            
            # 找到最优的合并配对
            for i in range(len(s)):
                for j in range(i + 1, min(i + k + 1, len(s))):
                    if s[i] == s[j]:
                        if best_left == -1 or i < best_left or (i == best_left and j < best_right):
                            best_left, best_right = i, j
            
            # 如果找到可合并的配对，执行合并
            if best_left != -1:
                s.pop(best_right)
                merged = True
        
        return ''.join(s)

public class Solution {
    public string MergeCharacters(string s, int k) {
        var chars = s.ToCharArray().ToList();
        bool merged = true;
        
        while (merged) {
            merged = false;
            int bestLeft = -1, bestRight = -1;
            
            // 找到最优的合并配对
            for (int i = 0; i < chars.Count; i++) {
                for (int j = i + 1; j < chars.Count && j - i <= k; j++) {
                    if (chars[i] == chars[j]) {
                        if (bestLeft == -1 || i < bestLeft || (i == bestLeft && j < bestRight)) {
                            bestLeft = i;
                            bestRight = j;
                        }
                    }
                }
            }
            
            // 如果找到可合并的配对，执行合并
            if (bestLeft != -1) {
                chars.RemoveAt(bestRight);
                merged = true;
            }
        }
        
        return new string(chars.ToArray());
    }
}

/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var mergeCharacters = function(s, k) {
    let arr = s.split('');
    
    while (true) {
        let found = false;
        let minLeft = Infinity;
        let minRight = Infinity;
        let leftIdx = -1, rightIdx = -1;
        
        for (let i = 0; i < arr.length; i++) {
            for (let j = i + 1; j < arr.length && j <= i + k; j++) {
                if (arr[i] === arr[j]) {
                    if (i < minLeft || (i === minLeft && j < minRight)) {
                        minLeft = i;
                        minRight = j;
                        leftIdx = i;
                        rightIdx = j;
                        found = true;
                    }
                }
            }
        }
        
        if (!found) break;
        
        arr.splice(rightIdx, 1);
    }
    
    return arr.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n³)最坏情况下需要进行O(n)轮合并，每轮需要O(n²)时间寻找配对
空间复杂度O(n)需要额外空间存储字符数组