Is Merge Close Characters II easy or hard?

It is rated Medium on FleetCode with an 84.1% acceptance rate. The problem is straightforward once you recognize it as a stack-based merging task, making it accessible for most candidates.

How to solve Merge Close Characters II in O(n)?

Use a stack or an in-place two-pointer approach. Iterate through each character once, compare it with the current top (or write pointer), and merge if they are close. Each character is pushed and popped at most once, giving linear time.

Merge Close Characters II Python/Java solution?

In Python, use a list as a stack and compare ord() values. In Java, use a StringBuilder or char array with a pointer. Both achieve O(n) time and O(1) space for the two-pointer variant.

What is the best approach for Merge Close Characters II?

The optimal approach is a single pass with a stack or an in-place two-pointer technique. Both run in O(n) time; the two-pointer version uses O(1) extra space by reusing the input string as the stack.

Is Merge Close Characters II asked at Google/Amazon/Meta?

While not confirmed for specific companies, this problem tests fundamental string manipulation and stack usage, which are common in technical interviews at top companies like Google, Amazon, and Meta.

What data structure is used in Merge Close Characters II?

A stack is commonly used to efficiently merge close characters. An alternative is to use an in-place two-pointer technique that simulates a stack without extra space.

What is the time complexity of Merge Close Characters II?

The optimal solution runs in O(n) time, where n is the length of the input string. The brute force approach runs in O(n^2) due to repeated shifting of characters after each merge.

4019. Merge Close Characters II - Practice Online

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 smallest i. If multiple pairs have the same i, choose the one with the smallest j.
Merge the right character into the left character by removing s[j] from s. The character s[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 because 3 - 0 = 3 <= k.
Remove the right 'a', resulting in s = "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 because 1 - 0 = 1 <= k.
Remove the right 'a', resulting in s = "abca".
The remaining 'a' characters are at indices 0 and 3. Since 3 - 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 because 1 - 0 = 1 <= k. This pair has the smallest left index among all close pairs.
Remove the right 'y', resulting in s = "ybyzybz".
The characters 'y' at indices 0 and 2 are now close because 2 - 0 = 2 <= k.
Remove the right 'y', resulting in s = "ybzybz".
No close pair remains, so no further merges are performed.

Constraints:

1 <= s.length <= 5 * 10⁵
1 <= k <= s.length
s consists of lowercase English letters.