Minimize The Integer (Codeforces 1251C)
Tags: Greedy, two pointers

You are given a huge integer $$$a$$$ consisting of $$$n$$$ digits ($$$n$$$ is between $$$1$$$ and $$$3 \cdot 10^5$$$, inclusive). It may contain leading zeros.You can swap two digits on adjacent (neighboring) positions if the swapping digits are of different parity (that is, they have different remainders when divided by $$$2$$$). For example, if $$$a = 032867235$$$ you can get the following integers in a single operation:   $$$302867235$$$ if you swap the first and the second digits;  $$$023867235$$$ if you swap the second and the third digits;  $$$032876235$$$ if you swap the fifth and the sixth digits;  $$$032862735$$$ if you swap the sixth and the seventh digits;  $$$032867325$$$ if you swap the seventh and the eighth digits. Note, that you can't swap digits on positions $$$2$$$ and $$$4$$$ because the positions are not adjacent. Also, you can't swap digits on positions $$$3$$$ and $$$4$$$ because the digits have the same parity.You can perform any number (possibly, zero) of such operations.Find the minimum integer you can obtain.Note that the resulting integer also may contain leading zeros.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input.The only line of each test case contains the integer $$$a$$$, its length $$$n$$$ is between $$$1$$$ and $$$3 \cdot 10^5$$$, inclusive.It is guaranteed that the sum of all values $$$n$$$ does not exceed $$$3 \cdot 10^5$$$.

Output: For each test case print line — the minimum integer you can obtain.

Note: In the first test case, you can perform the following sequence of operations (the pair of swapped digits is highlighted): $$$0 \underline{\textbf{70}} 9 \rightarrow 0079$$$.In the second test case, the initial integer is optimal. In the third test case you can perform the following sequence of operations: $$$246 \underline{\textbf{43}} 2 \rightarrow 24 \underline{\textbf{63}}42 \rightarrow 2 \underline{\textbf{43}} 642 \rightarrow 234642$$$.

Sample Inputs:
3
0709
1337
246432

Sample Outputs:
0079
1337
234642

Solution (Python):
from sys import stdin

def main():
    data = stdin.read().splitlines()[1:]
    for (ii, s) in enumerate(data):
        (gf, n) = (([], []), len(s))
        for c in s:
            gf[ord(c) & 1].append(c)
        (g, f) = gf
        g.append('a')
        f.append('a')
        g.reverse()
        f.reverse()
        data[ii] = ''.join((f.pop() if f[-1] < g[-1] else g.pop() for _ in range(n)))
    print('\n'.join(map(str, data)))
if __name__ == '__main__':
    main()

Solution (Python):
t = int(input())

def f(s):
    evens = []
    odds = []
    for digit in s:
        if int(digit) % 2 == 0:
            evens.append(digit)
        else:
            odds.append(digit)
    (i, j) = (0, 0)
    result = ''
    while i < len(odds) and j < len(evens):
        if odds[i] < evens[j]:
            result += odds[i]
            i += 1
        else:
            result += evens[j]
            j += 1
    result += ''.join(odds[i:])
    result += ''.join(evens[j:])
    return result
for _ in range(t):
    s = input().strip()
    result = f(s)
    print(result)

Solution (Python):
from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(10 ** 6)
import threading
input = stdin.readline

def ii():
    return int(input())

def lii():
    return list(map(int, stdin.readline().split()))

def ss():
    x = stdin.readline()
    if x and x[-1] == '\n':
        return x[:-1]
    return x

def lss():
    return list(map(str, stdin.readline().split()))

def llss():
    return [i for i in ss()]

def mpi():
    return map(int, input().split())

def yes(flag):
    if flag:
        stdout.write('YES\n')
    else:
        stdout.write('NO\n')

def pl(lst):
    stdout.write(' '.join(map(str, lst)) + '\n')

def ps(n):
    stdout.write(str(n) + '\n')
from collections import defaultdict, deque
import heapq

def main():
    for _ in range(ii()):
        s = ss()
        (l, r) = ('', '')
        for i in s:
            if int(i) % 2:
                l += i
            else:
                r += i
        ans = ''
        (i, j) = (0, 0)
        while i < len(l) and j < len(r):
            if l[i] < r[j]:
                ans += l[i]
                i += 1
            else:
                ans += r[j]
                j += 1
        ans += l[i:] + r[j:]
        print(ans)
threading.stack_size(2 * 10 ** 6)
t = threading.Thread(target=main)
t.start()
t.join()