leetcode 4019 Merge Close Characters II | linear scan
Merge Close Characters II - Video Solution
Watch the video solution for Merge Close Characters II, a medium level problem. This walkthrough by Code-Yao has 2 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 smallesti. If multiple pairs have the samei, choose the one with the smallestj. - Merge the right character into the left character by removing
s[j]froms. The characters[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 because3 - 0 = 3 <= k. - Remove the right
'a', resulting ins = "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 because1 - 0 = 1 <= k. - Remove the right
'a', resulting ins = "abca". - The remaining
'a'characters are at indices 0 and 3. Since3 - 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 because1 - 0 = 1 <= k. This pair has the smallest left index among all close pairs. - Remove the right
'y', resulting ins = "ybyzybz". - The characters
'y'at indices 0 and 2 are now close because2 - 0 = 2 <= k. - Remove the right
'y', resulting ins = "ybzybz". - No close pair remains, so no further merges are performed.
Constraints:
1 <= s.length <= 5 * 1051 <= k <= s.lengthsconsists of lowercase English letters.
Approach Overview
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.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force (Iterative Merging) | O(n^2) | O(n) | Small inputs or conceptual clarity |
| Stack-Based | O(n) | O(n) | General case, clean implementation |
| In-Place Two Pointer | O(n) | O(1) | Memory-constrained environments or interviews |