Lex String (Codeforces 1689A)
Tags: Greedy, two pointers

Kuznecov likes art, poetry, and music. And strings consisting of lowercase English letters.Recently, Kuznecov has found two strings, $$$a$$$ and $$$b$$$, of lengths $$$n$$$ and $$$m$$$ respectively. They consist of lowercase English letters and no character is contained in both strings. Let another string $$$c$$$ be initially empty. Kuznecov can do the following two types of operations:  Choose any character from the string $$$a$$$, remove it from $$$a$$$, and add it to the end of $$$c$$$.  Choose any character from the string $$$b$$$, remove it from $$$b$$$, and add it to the end of $$$c$$$. But, he can not do more than $$$k$$$ operations of the same type in a row. He must perform operations until either $$$a$$$ or $$$b$$$ becomes empty. What is the lexicographically smallest possible value of $$$c$$$ after he finishes?A string $$$x$$$ is lexicographically smaller than a string $$$y$$$ if and only if one of the following holds: $$$x$$$ is a prefix of $$$y$$$, but $$$x \neq y$$$;  in the first position where $$$x$$$ and $$$y$$$ differ, the string $$$x$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$y$$$.

Input: There are several test cases in the input data. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. This is followed by the test cases description.The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1\leq n,m,k \leq 100$$$) — parameters from the statement.The second line of each test case contains the string $$$a$$$ of length $$$n$$$.The third line of each test case contains the string $$$b$$$ of length $$$m$$$. The strings contain only lowercase English letters. It is guaranteed that no symbol appears in $$$a$$$ and $$$b$$$ simultaneously.

Output: In each test case, output a single string $$$c$$$ — the answer to the problem.

Note: In the first test case, it is optimal to take two 'a's from the string $$$a$$$ and add them to the string $$$c$$$. Then it is forbidden to take more characters from $$$a$$$, hence one character 'b' from the string $$$b$$$ has to be taken. Following that logic, we end up with $$$c$$$ being 'aabaabaa' when string $$$a$$$ is emptied.In the second test case it is optimal to take as many 'a's from string $$$a$$$ as possible, then take as many 'b's as possible from string $$$b$$$. In the end, we take two 'c's from the string $$$a$$$ emptying it. 

Sample Inputs:
3
6 4 2
aaaaaa
bbbb
5 9 3
caaca
bedededeb
7 7 1
noskill
wxhtzdy

Sample Outputs:
aabaabaa
aaabbcc
dihktlwlxnyoz

Solution (Python):
def solve(a, b, operations):
    a = list(a)
    a.sort()
    a = ''.join(a)
    b = list(b)
    b.sort()
    b = ''.join(b)
    result = ''
    last_operation = 'a'
    k = 0
    while len(a) > 0 and len(b) > 0:
        if (k == operations and last_operation == 'b' or a[0] < b[0]) and (k < operations or last_operation != 'a'):
            if last_operation == 'a':
                k += 1
            else:
                k = 1
            last_operation = 'a'
            result += a[0]
            if len(a) == 1:
                a = ''
            else:
                a = a[1:]
        else:
            if last_operation == 'b':
                k += 1
            else:
                k = 1
            last_operation = 'b'
            result += b[0]
            if len(b) == 1:
                b = ''
            else:
                b = b[1:]
    return result

def main():
    tests = int(input())
    for _ in range(tests):
        (n, m, k) = map(int, input().split())
        print(solve(input(), input(), k))
if __name__ == '__main__':
    main()

Solution (Python):
def solve():
    (n, m, k) = [int(x) for x in input().split()]
    a = sorted(input())
    b = sorted(input())
    c = ''
    (Ai, Bi, curK, curPointer) = (0, 0, 0, 0)
    while Ai < n and Bi < m:
        if a[Ai] < b[Bi] and (curPointer == 1 or (curPointer == 0 and curK < k)) or (curPointer == 1 and curK >= k):
            if curPointer == 1:
                curK = 1
                curPointer = 0
            else:
                curK += 1
            c += a[Ai]
            Ai += 1
        else:
            if curPointer == 0:
                curK = 1
                curPointer = 1
            else:
                curK += 1
            c += b[Bi]
            Bi += 1
    print(c)
for _ in range(int(input())):
    solve()

Solution (Python):
""""""

def slv():
    (n, m, k) = map(int, input().split())
    a = sorted(input())
    b = sorted(input())
    (x, y, i, j) = (0, 0, 0, 0)
    ans = []
    while i < n and j < m:
        if a[i] < b[j] and x < k or y == k:
            ans.append(a[i])
            i += 1
            x += 1
            y = 0
        else:
            ans.append(b[j])
            j += 1
            y += 1
            x = 0
    print(*ans, sep='')
if __name__ == '__main__':
    t = 1
    t = int(input())
    while t > 0:
        slv()
        t -= 1