📘 題目敘述
給你一個只包含小寫英文字母的字串 s，以及一個整數
k。
在目前的字串 s 中，兩個相同字元如果它們的索引距離最多為
k，則稱它們是 close。當兩個字元是 close
時，右邊那個會合併到左邊那個，直到不能再合併為止。
若同時有多個合併可能，永遠先合併左端索引最小的一對；若左端相同，則選右端索引最小的一對。
條件限制
1 <= s.length <= 1001 <= k <= s.lengths只包含小寫英文字母
🧠 解題思路
我這份寫法是用長度最多為
k 的滑動視窗去模擬：在目前位置往回看
k 個字元內，有沒有出現過相同字元。
我用 queue<char> q 記錄最近加入答案的字元，再用
set<char> ss 快速判斷某字元是否在視窗內。
所有變數
-
q：存最近加入答案的字元，維持最多k個 -
ss：存q裡有哪些字元，用來快速判斷 ans：最後要回傳的結果字串
🪜 主要流程步驟
1. 初始化視窗與答案
建立空的 queue、set 與答案字串
ans。
2. 逐字掃描 s
如果目前字元已經在 ss 內，代表距離
k 內有同字元，它會被合併，不加入答案。
3. 視窗滿時先移除最舊字元
當視窗大小等於 k 且新字元不在
ss 時，先彈出最舊字元，再把新字元加入。
4. 視窗未滿時直接加入
當視窗未滿且字元不在 ss 中，直接加入
q、ss 和 ans。
5. 回傳 ans
掃描結束後回傳 ans。
⏱️ 複雜度
- 時間複雜度：
O(n log k) - 空間複雜度：
O(k)
💻 程式碼實作
class Solution {
public:
string mergeCharacters(string s, int k) {
queue<char> q;
set<char> ss;
string ans = "";
for (char a : s) {
if (q.size() == k) {
if (!ss.count(a)) {
ss.erase(q.front());
q.pop();
q.push(a);
ss.insert(a);
ans += a;
}
}
if (q.size() < k && !ss.count(a)) {
q.push(a);
ss.insert(a);
ans += a;
}
}
return ans;
}
};🔗 題目連結
https://leetcode.com/contest/biweekly-contest-177/problems/merge-close-characters/