4019. Merge Close Characters II 🔒

Description

You are given a string s consisting of lowercase English letters and an integer k.

Two equal characters s[i] and s[j], where 0 <= i < j < s.length, are considered close if j - i <= k. All indices refer to the current string.

Repeatedly perform the following operation until no close pair remains:

Among all close pairs (i, j), choose the pair with the smallest i. If multiple pairs have the same i, choose the one with the smallest j.
Merge the right character into the left character by removing s[j] from s. The character s[i] remains unchanged, and the remaining characters are reindexed.

Return the resulting string after performing all possible merges.

Example 1:

Input: s = "abca", k = 3

Output: "abc"

Explanation:

The characters 'a' at indices 0 and 3 are close because 3 - 0 = 3 <= k.
Remove the right 'a', resulting in s = "abc".
No close pair remains, so no further merges are performed.

Example 2:

Input: s = "aabca", k = 2

Output: "abca"

Explanation:

The characters 'a' at indices 0 and 1 are close because 1 - 0 = 1 <= k.
Remove the right 'a', resulting in s = "abca".
The remaining 'a' characters are at indices 0 and 3. Since 3 - 0 = 3 > k, no further merges are performed.

Example 3:

Input: s = "yybyzybz", k = 2

Output: "ybzybz"

Explanation:

The characters 'y' at indices 0 and 1 are close because 1 - 0 = 1 <= k. This pair has the smallest left index among all close pairs.
Remove the right 'y', resulting in s = "ybyzybz".
The characters 'y' at indices 0 and 2 are now close because 2 - 0 = 2 <= k.
Remove the right 'y', resulting in s = "ybzybz".
No close pair remains, so no further merges are performed.

Constraints:

1 <= s.length <= 5 * 10⁵
1 <= k <= s.length
s consists of lowercase English letters.

Solutions

Solution 1: Hash Table

We use a hash table \(\textit{last}\) to record the last occurrence position of each character in the answer string. We iterate over each character in \(s\) from left to right. Let \(\textit{cur}\) be the current length of the answer. If the character has appeared before and the difference between \(\textit{cur}\) and its last occurrence is at most \(k\), we skip it; otherwise, we append the character to the answer and update its position in the hash table.

Each merge always removes the right character, so the positions in the answer are exactly the indices in the current string. This greedy process is equivalent to repeatedly performing the required merge operations.

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. Merge Close Characters II 🔒

Description

Solutions

Solution 1: Hash Table

Comments