Forbidden Subsequence (Codeforces 1617A)
Tags: Greedy, strings

You are given strings $$$S$$$ and $$$T$$$, consisting of lowercase English letters. It is guaranteed that $$$T$$$ is a permutation of the string abc. Find string $$$S'$$$, the lexicographically smallest permutation of $$$S$$$ such that $$$T$$$ is not a subsequence of $$$S'$$$.String $$$a$$$ is a permutation of string $$$b$$$ if the number of occurrences of each distinct character is the same in both strings.A string $$$a$$$ is a subsequence of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements.A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds: $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$; in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Description of the test cases follows.The first line of each test case contains a string $$$S$$$ ($$$1 \le |S| \le 100$$$), consisting of lowercase English letters.The second line of each test case contains a string $$$T$$$ that is a permutation of the string abc. (Hence, $$$|T| = 3$$$).Note that there is no limit on the sum of $$$|S|$$$ across all test cases.

Output: For each test case, output a single string $$$S'$$$, the lexicographically smallest permutation of $$$S$$$ such that $$$T$$$ is not a subsequence of $$$S'$$$.

Note: In the first test case, both aaaabbc and aaaabcb are lexicographically smaller than aaaacbb, but they contain abc as a subsequence.In the second test case, abccc is the smallest permutation of cccba and does not contain acb as a subsequence.In the third test case, bcdis is the smallest permutation of dbsic and does not contain bac as a subsequence.

Sample Inputs:
7
abacaba
abc
cccba
acb
dbsic
bac
abracadabra
abc
dddddddddddd
cba
bbc
abc
ac
abc

Sample Outputs:
aaaacbb
abccc
bcdis
aaaaacbbdrr
dddddddddddd
bbc
ac

Solution (Python):
def solve():
    s = input()
    t = input()
    if not 'a' in s or not 'b' in s or (not 'c' in s):
        print(''.join(sorted(list(s))))
    elif t == 'abc':
        print('a' * s.count('a') + 'c' * s.count('c') + 'b' * s.count('b') + ''.join(sorted(list(s))).replace('a', '').replace('b', '').replace('c', ''))
    else:
        print(''.join(sorted(list(s))))
if __name__ == '__main__':
    for test in range(int(input())):
        solve()

Solution (Python):
def solve():
    s = input()
    t = input()
    if not 'a' in s or not 'b' in s or (not 'c' in s):
        print(''.join(sorted(list(s))))
    elif t == 'abc':
        print('a' * s.count('a') + 'c' * s.count('c') + 'b' * s.count('b') + ''.join(sorted(list(s))).replace('a', '').replace('b', '').replace('c', ''))
    else:
        print(''.join(sorted(list(s))))
if __name__ == '__main__':
    for test in range(int(input())):
        solve()

Solution (Python):
for i in range(int(input())):
    s = ''.join(sorted(input()))
    d = input()
    a = s.count('a')
    b = s.count('b')
    c = s.count('c')
    if d != 'abc' or a * b * c == 0:
        print(s)
    else:
        a = s.count('a')
        b = s.count('b')
        c = s.count('c')
        print(a * 'a' + c * 'c' + b * 'b' + s[a + b + c:])