Merge Close Characters II - Solution & Explanation

Problem Overview: Merge Close Characters II asks you to merge adjacent characters in a string when they are considered "close" based on a given distance threshold, producing a condensed output string while preserving the order of the remaining characters.

Approach 1: Brute Force - Iterative Merging (O(n^2) time, O(n) space)

Start from the leftmost character and compare it with the next character. If the absolute difference in their ASCII values is less than or equal to the given threshold, merge them by removing the second character and stay at the same index to compare the merged character with the next one. This requires repeatedly shifting all subsequent characters, leading to O(n) shifts per merge and O(n^2) worst-case time. Use this only if the input is extremely small or you need a quick conceptual baseline.

Approach 2: Optimal - Single Pass with Stack (O(n) time, O(n) space)

Use a stack to build the result incrementally. Iterate through each character in the string. For each character, check if it is close to the current top of the stack (i.e., absolute difference <= threshold). If it is close, pop the top and push the merged character (e.g., the later character or a combined representation). If not close, push the current character onto the stack. After processing all characters, the stack contains the final merged string in reverse order; reverse it to get the answer. This approach processes each character exactly once and each stack operation is O(1), yielding O(n) time and O(n) space for the stack.

Approach 3: Optimal - In-Place Two Pointer (O(n) time, O(1) space)

Instead of using an explicit stack, maintain a write pointer i that acts as the top of an implicit stack within the original string. Iterate with a read pointer j from 1 to n-1. At each step, compare s[j] with s[i]. If they are close, merge them by updating s[i] to the merged result and do not increment i. If they are not close, increment i and copy s[j] to s[i]. After the loop, the first i+1 characters form the answer. This avoids extra space and is the most memory-efficient solution.

Recommended for interviews: The two-pointer or stack approach is what interviewers expect. The brute force shows you understand the problem but fails for large inputs. The stack approach demonstrates clean use of a classic data structure, while the two-pointer shows deeper optimization. Both are O(n) time; choose two-pointer if you want to highlight space optimization.

Related topics: string manipulation, stack, two pointers.