Problem Statement in English

You are given a string s and an integer k. You can perform the following operation on s any number of times:

  • Choose two indices i and j such that 0 <= i < j < s.length and s[i] == s[j]. Then, merge the the character at index j with the character at index i and remove the character at index j from s.

Return the resulting string after performing the operation until you can no longer perform it.

Approach

This is a stack question.

We just iterate over the string and maintain a hashmap to store the last index of each character.

We also maintain a reduction variable to keep track of how many characters we have removed from the string. This is because the index of subsequent characters will change after we remove characters from the string. To be precise, they will decrease by the number of characters we have removed from the string.

If the last time we saw the current character is within k distance from the current index (after accounting for the reduction), then we can merge the characters and remove the current character from the string. We also update the reduction variable.

If the last time we saw the current character is not within k distance from the current index, then we update the last index of the current character in the hashmap and add the current character to the stack.

Finally, we join the characters in the stack to get the resulting string.

And we’re done!

Solution in Python


class Solution:
    def mergeCharacters(self, s: str, k: int) -> str:
        stack = []
        hm = {}

        reduction = 0

        for i in range(len(s)):
            c = s[i]

            if c in hm and i - reduction - hm[c] <= k:
                reduction += 1
            else:
                hm[c] = i - reduction
                stack.append(c)

        return "".join(stack)

Complexity

  • Time: $O(n)$
    Since we iterate over the string once.

  • Space: $O(n)$
    Since we store the stack and the hashmap.

And we are done.