LeetCode 3853 - Merge Close Characters

Difficulty: 🟡 Medium
Topics: Hash Table, String

Solution

Problem Understanding

The problem asks us to repeatedly merge close, equal characters in a string s. A character pair is considered close if the distance between their indices is at most k. When a merge occurs, the right character is removed and the string is updated immediately. Merges are performed one at a time, always choosing the pair with the smallest left index, and if tied, the smallest right index.

The input consists of a string s of lowercase letters and an integer k. The output is a string after performing all possible merges according to the rules. Given the constraints (1 <= s.length <= 100), the string is short, but the merging process may involve repeated scanning of the string.

Important observations:

The string length is small (max 100), so even an approach that scans repeatedly can be acceptable if it is implemented carefully.
Characters merge one at a time, and each merge changes the indices of remaining characters, so the process is dynamic.
Edge cases include strings where multiple characters are equal and close at multiple positions, strings where no merges occur, and k values equal to 1 or equal to s.length.

Approaches

Brute Force Approach

A naive solution repeatedly scans the string for all pairs of equal characters within distance k. Once a merge is found (choosing the leftmost first, then rightmost if tied), the right character is removed, and the scan starts over. This guarantees correctness because it directly simulates the problem statement.

The drawback is that each scan can take O(n^2) in the worst case, and we may need up to O(n) iterations, resulting in a worst-case complexity of O(n^3). For n <= 100, this is acceptable but not elegant.

Optimal Approach

The key insight is that we can use a stack to maintain characters of the resulting string as we iterate. For each character, we compare it with previous occurrences stored in the stack and check if the distance is within k. If so, we merge (skip adding the current character). This allows us to handle the dynamic index shifts automatically, as the stack represents the current merged string.

This approach guarantees leftmost merges first because the stack always considers the earliest character in the current result. It is efficient because we only iterate over the string once and use a map to track the last occurrence of each character for fast distance checks.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(n)	Repeatedly scans string and removes characters one by one
Optimal	O(n^2)	O(n)	Uses stack and last index tracking to merge efficiently

Algorithm Walkthrough

Initialize an empty stack res to store the resulting string characters.
Initialize a dictionary last_index to store the last index of each character in res.
Iterate over the string s with index i and character c.
For each character c, check if c exists in last_index. If it does, calculate the distance between i and the last occurrence index.
If the distance <= k, skip adding c to res (merge occurs).
Otherwise, add c to res and update last_index[c] to the current index in res.
After iterating through the string, convert the stack res to a string and return it.

Why it works: The stack always maintains the merged string state, and the last index dictionary ensures we only merge characters that are close according to k. Since merges happen one at a time and leftmost-first, this approach respects the rules.

Python Solution

class Solution:
    def mergeCharacters(self, s: str, k: int) -> str:
        res = []
        last_index = {}
        for c in s:
            if c in last_index and len(res) - last_index[c] <= k:
                # Merge: skip adding this character
                continue
            last_index[c] = len(res)
            res.append(c)
        return ''.join(res)

Implementation walkthrough: We maintain a list res as our stack to build the resulting string. last_index tracks the position of each character in res. For each character c, we check if it has appeared recently within distance k. If so, we skip it to simulate merging. Otherwise, we append c and update its index. Finally, we join res into a string.

Go Solution

func mergeCharacters(s string, k int) string {
    res := []byte{}
    lastIndex := make(map[byte]int)
    for i := 0; i < len(s); i++ {
        c := s[i]
        if idx, ok := lastIndex[c]; ok && len(res)-idx <= k {
            continue
        }
        lastIndex[c] = len(res)
        res = append(res, c)
    }
    return string(res)
}

Go-specific notes: We use a map[byte]int for last occurrence tracking. The stack is represented by a byte slice res, which we append to dynamically. The len(res)-idx <= k condition checks closeness similar to Python.

Worked Examples

Example 1: s = "abca", k = 3

Step	res	last_index	Action
'a'	['a']	{'a':0}	add 'a'
'b'	['a','b']	{'a':0,'b':1}	add 'b'
'c'	['a','b','c']	{'a':0,'b':1,'c':2}	add 'c'
'a'	['a','b','c']	{'a':0,'b':1,'c':2}	distance 3 <= k, merge

Result: "abc"

Example 2: s = "aabca", k = 2

Step	res	last_index	Action
'a'	['a']	{'a':0}	add 'a'
'a'	['a']	{'a':0}	distance 1 <= k, merge
'b'	['a','b']	{'a':0,'b':1}	add 'b'
'c'	['a','b','c']	{'a':0,'b':1,'c':2}	add 'c'
'a'	['a','b','c','a']	{'a':3,'b':1,'c':2}	distance 3 > k, add

Result: "abca"

Example 3: s = "yybyzybz", k = 2

Step	res	last_index	Action
'y'	['y']	{'y':0}	add 'y'
'y'	['y']	{'y':0}	distance 1 <= k, merge
'b'	['y','b']	{'y':0,'b':1}	add 'b'
'y'	['y','b','y']	{'y':2,'b':1}	distance 2 <= k, merge
'z'	['y','b','z']	{'y':2,'b':1,'z':2}	add 'z'
'y'	['y','b','z','y']	{'y':3,'b':1,'z':2}	distance 1 <= k, merge
'b'	['y','b','z','b']	{'y':3,'b':3,'z':2}	distance 2 <= k, merge
'z'	['y','b','z','z']	{'y':3,'b':3,'z':3}	distance 1 <= k, merge

Result: "ybzybz"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	For each character, we may check closeness using the last index in the current result stack; worst-case linear checks per character.
Space	O(n)	Stack `res` and dictionary `last_index` each store at most `n` elements.

The approach is acceptable for n <= 100 and avoids unnecessary repeated full string scans.

Test Cases

# Provided examples
assert Solution().mergeCharacters("abca", 3) == "abc"  # merge distant 'a'
assert Solution().mergeCharacters("aabca", 2) == "abca"  # merge consecutive 'a's
assert Solution().mergeCharacters("yybyzybz", 2) == "ybzybz"  # multiple merges

# Edge cases
assert Solution().mergeCharacters("a", 1) == "a"  # single character, nothing to merge
assert Solution().mergeCharacters("aa", 1) == "a"  # two identical, merge occurs
assert Solution().mergeCharacters("abc", 3) == "abc"  # no merges, all distinct
assert Solution().mergeCharacters("aaaaa", 1) == "a