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

Two equal characters in the current string s are considered close if the distance between their indices is at most k.

When two characters are close, the right one merges into the left. Merges happen one at a time, and after each merge, the string updates until no more merges are possible.

Return the resulting string after performing all possible merges.

Note: If multiple merges are possible, always merge the pair with the smallest left index. If multiple pairs share the smallest left index, choose the pair with the smallest right index.

In other words, you process the string from left to right and build up a result. For each character, you check its last position in the result you have built so far. If the same character appeared recently enough — that is, the distance between the current position in the result and its previous position is at most k — then this character is merged away and discarded. Otherwise, the character is kept and becomes part of the result, updating its latest recorded position.

For example, suppose s = "aabba" and k = 1:

• Place a at index 0.
• The next a would land at index 1, and 1 - 0 = 1 <= k, so it merges away.
• Place b at index 1.
• The next b would land at index 2, and 2 - 1 = 1 <= k, so it merges away.
• The final a would land at index 2, but a was last at index 0, and 2 - 0 = 2 > k, so it is kept.

The resulting string is "aba".

The task is to compute this final merged string after no further merges can be performed.

At first glance, the problem describes a complicated process: repeatedly find the closest pair of equal characters, merge the right one into the left, and rebuild the string after every single merge. Simulating this literally would be slow and tricky to manage, because every merge changes the indices of all the characters that follow.

The key insight comes from carefully reading the merge rule. We must always merge the pair with the smallest left index first, and among those, the pair with the smallest right index. This ordering means the merging effectively happens in a strict left-to-right order. As we scan the string from the beginning, each character is decided before we move on to the next one — there is no need to go back.

This naturally suggests building the answer incrementally. We maintain a result list ans that holds the characters we have decided to keep. When we look at a new character c, the position it would occupy in the result is cur = len(ans). The question becomes: should this character merge into a previous equal character, or should it survive?

A character c merges away only if an equal character already exists in the result and is close to it — meaning the distance cur - last[c] is at most k, where last[c] is the most recent position of c in the result. If that condition holds, the current character is absorbed and we simply skip it. Otherwise, it is far enough away (or has never appeared), so we keep it.

To check the closeness condition instantly, we only need to remember where each character last landed in the result. A hash table last mapping each character to its latest position in ans does exactly this. Every time we keep a character, we update its recorded position, so future checks always compare against the correct, most recent location.

This transforms a seemingly heavy simulation into a single clean pass over the string. By processing characters one at a time and tracking only the last position of each character, we capture the entire merging behavior without ever rebuilding the string, arriving at the final result in linear time.

Solution 1: Hash Table

We use a hash table last to record the last occurrence position of each character within the result we are building. We iterate over each character in the string. If the current character has appeared before and the difference between its position in the result and its last recorded position is at most k, we skip the character; otherwise, we add the character to the answer and update its position in the hash table.

Let's walk through the implementation step by step:

1. Initialize the data structures.

   • last = {} is a hash table mapping each character to its most recent position in the result list.
   • ans = [] is a list that stores the characters we decide to keep, which will be joined into the final string.

2. Iterate over each character c in s.

   • Compute cur = len(ans), which is the index this character would take if it were appended to the result. This value represents the character's position in the current string after all prior merges, which is exactly what the closeness check needs.

3. Decide whether the character merges away or survives.

   • Check the condition c in last and cur - last[c] <= k.
     • c in last confirms that an equal character already exists in the result.
     • cur - last[c] <= k confirms that the previous equal character is close — within distance k of the current position.
   • If both hold, the character is absorbed by the earlier one, so we continue and skip it entirely.

4. Keep the character when it cannot merge.

   • If the condition fails (the character is new or too far away), we append it to ans and update last[c] = cur to record its new latest position. Future characters will compare against this updated position.

5. Build and return the result.

   • After the loop finishes, ans holds all surviving characters in order. We return "".join(ans) as the final merged string.

Because each character's position in the result is fixed the moment it is kept, the value last[c] always reflects the correct distance for the next comparison. This avoids ever rebuilding the string after a merge.

The time complexity is O(n), where n is the length of the string s, since we make a single pass and each hash table operation is O(1). The space complexity is O(|\Sigma|), where |\Sigma| is the size of the character set (at most 26 for lowercase English letters), used by the hash table last. The result list itself takes O(n) space in the worst case.