To construct the lexicographically smallest string by merging two given strings a and b, we must carefully manage how many consecutive characters we take from each. We always aim to take the smallest available character to maintain lexicographical order. However, if we have already taken k consecutive characters from one string (say A = k from a), we are forced to pick the next smallest character from b, even if a has a smaller character. The same rule applies if B = k, requiring us to take from a instead. Each time we switch between the two strings, we reset the counter for the previous one, ensuring that we do not exceed the limit of k consecutive picks. This approach guarantees that we construct the smallest possible string while adhering to the constraint on consecutive selections. By maintaining counters for consecutive selections and always prioritizing the smallest character while respecting the constraints, we efficiently merge the two strings optimally.

t = int(input()) for _ in range(t): n, m, k = map(int, input().split()) string_a = list(input().strip()) string_b = list(input().strip()) string_a.sort(reverse=True) string_b.sort(reverse=True)

consecutive_a = 0
consecutive_b = 0
result = []

while string_a and string_b:
    # Determine which string has the smaller character at the end
    pick_from_b = string_b[-1] < string_a[-1]

    if pick_from_b and consecutive_b == k:
        pick_from_b = False
    if not pick_from_b and consecutive_a == k:
        pick_from_b = True

    if pick_from_b:
        result.append(string_b.pop())
        consecutive_b += 1
        consecutive_a = 0
    else:
        result.append(string_a.pop())
        consecutive_a += 1
        consecutive_b = 0

print("".join(result))

Define the pattern of a (validly) folded strip to be the set of characters, in order, seen from above after all folds are made.

It is always possible to fold the strip in such a way that no two adjacent characters in the pattern are equal. If we fold in between every pair of equal characters, and don't fold in between every pair of distinct characters, we will achieve this.

Also, there is only one obtainable pattern that is alternating in this way. It is never possible to fold in between two adjacent different characters, because that can never be part of a valid folding, and if there exists a pair of adjacent equal characters that you don't fold in between, the pattern will not be alternating.

To achieve this folding we can consider a segment as a contiguous section of the pattern that has alternating symbols. We can fold each segment on top of each other and obtain the optimal string as the length of the longest alternating section. to keep track of this we can count the patterns that have 0's at the even indexes and 1's at the odd indexes as a positive offset on a variable and count the length of the pattern's that have 0's at the odd indexes and 1's at the even indexes as a negative offset. The difference between the maximum offset and the minimum offset will give us the longest alternating offset which will be the answer.

Complexity: $$$O(n)$$$

t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    offset = 0
    mx = 0
    mn = 0
    for i in range(n):
        c = s[i]
        if (c=='1' and i%2) or (c == '0' and i%2 == 0):
            offset+=1
        else:
            offset-=1
        mn = min(offset,mn)
        mx = max(offset,mx)
    print(mx-mn)