Kill Anton (Codeforces 1526D)
Tags: Math, strings

After rejecting $$$10^{100}$$$ data structure problems, Errorgorn is very angry at Anton and decided to kill him.Anton's DNA can be represented as a string $$$a$$$ which only contains the characters "ANTON" (there are only $$$4$$$ distinct characters). Errorgorn can change Anton's DNA into string $$$b$$$ which must be a permutation of $$$a$$$. However, Anton's body can defend against this attack. In $$$1$$$ second, his body can swap $$$2$$$ adjacent characters of his DNA to transform it back to $$$a$$$. Anton's body is smart and will use the minimum number of moves.To maximize the chance of Anton dying, Errorgorn wants to change Anton's DNA the string that maximizes the time for Anton's body to revert his DNA. But since Errorgorn is busy making more data structure problems, he needs your help to find the best string $$$B$$$. Can you help him?

Input: The first line of input contains a single integer $$$t$$$ $$$(1 \leq t \leq 100000)$$$ — the number of testcases.The first and only line of each testcase contains $$$1$$$ string $$$a$$$ ($$$1 \leq |a| \leq 100000$$$). $$$a$$$ consists of only the characters "A", "N", "O" and "T".It is guaranteed that the sum of $$$|a|$$$ over all testcases does not exceed $$$100000$$$.

Output: For each testcase, print a single string, $$$b$$$. If there are multiple answers, you can output any one of them. $$$b$$$ must be a permutation of the string $$$a$$$.

Note: For the first testcase, it takes $$$7$$$ seconds for Anton's body to transform NNOTA to ANTON: NNOTA $$$\to$$$ NNOAT $$$\to$$$ NNAOT $$$\to$$$ NANOT $$$\to$$$ NANTO $$$\to$$$ ANNTO $$$\to$$$ ANTNO $$$\to$$$ ANTON. Note that you cannot output strings such as AANTON, ANTONTRYGUB, AAAAA and anton as it is not a permutation of ANTON.For the second testcase, it takes $$$2$$$ seconds for Anton's body to transform AANN to NAAN. Note that other strings such as NNAA and ANNA will also be accepted.

Sample Inputs:
4
ANTON
NAAN
AAAAAA
OAANTTON

Sample Outputs:
NNOTA
AANN
AAAAAA
TNNTAOOA

Solution (Python):
def naiveSolve(n):
    return
from itertools import permutations
from collections import Counter

def solve(s):
    n = len(s)
    chars = list(set(s))
    m = len(chars)
    charCnts = Counter(s)
    optimalAns = ''
    optimalMoves = -1
    for perm in permutations(chars):
        chars = list(perm)
        charMap = {x: i for (i, x) in enumerate(perm)}
        convertedS = [charMap[x] for x in s]
        moves = 0
        suffixNumCnts = [0] * m
        for i in range(n - 1, -1, -1):
            for j in range(m):
                if j < convertedS[i]:
                    moves += suffixNumCnts[j]
            suffixNumCnts[convertedS[i]] += 1
        if moves > optimalMoves:
            ss = []
            for x in perm:
                for _ in range(charCnts[x]):
                    ss.append(x)
            optimalAns = ''.join(ss)
            optimalMoves = moves
    return optimalAns

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        allans.append(solve(input()))
    multiLineArrayPrint(allans)
    return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
    print('? {} {}'.format(i, j))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(' '.join([str(x) for x in ans])))
    sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
from math import gcd, floor, ceil
for _abc in range(1):
    main()

Solution (Python):
def naiveSolve(n):
    return

def verifyCnt(s, target):
    arr = list(s)
    n = len(s)
    cnt = 0
    for i in range(n):
        if arr[i] == target[i]:
            continue
        for j in range(i + 1, n):
            cnt += 1
            if arr[j] == target[i]:
                arr.pop(j)
                arr.insert(i, target[i])
                break
    return cnt
from itertools import permutations
from collections import Counter

def solve(s):
    n = len(s)
    chars = list(set(s))
    m = len(chars)
    charCnts = Counter(s)
    optimalAns = ''
    optimalMoves = -1
    for perm in permutations(chars):
        chars = list(perm)
        charMap = {x: i for (i, x) in enumerate(perm)}
        convertedS = [charMap[x] for x in s]
        target = []
        for (i, x) in enumerate(perm):
            for cnts in range(charCnts[x]):
                target.append(i)
        moves = 0
        suffixNumCnts = [0] * m
        for i in range(n - 1, -1, -1):
            for j in range(m):
                if j < convertedS[i]:
                    moves += suffixNumCnts[j]
            suffixNumCnts[convertedS[i]] += 1
        if moves > optimalMoves:
            ss = ''.join([chars[i] for i in target])
            optimalAns = ss
            optimalMoves = moves
    return optimalAns

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        allans.append(solve(input()))
    multiLineArrayPrint(allans)
    return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
    print('? {} {}'.format(i, j))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(' '.join([str(x) for x in ans])))
    sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
from math import gcd, floor, ceil
for _abc in range(1):
    main()

Solution (Python):
import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
from itertools import permutations, combinations

def data():
    return sys.stdin.readline().strip()

def mdata():
    return list(map(int, data().split()))

def outl(var):
    sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
    sys.stdout.write(str(var) + '\n')
INF = float('inf')
mod = int(1000000000.0) + 7
for t in range(int(data())):
    a = data()
    m = [[0] * 26 for i in range(26)]
    d = dd(int)
    for i in a:
        s = ord(i) - 65
        for j in range(26):
            if s != j:
                m[s][j] += m[j][j]
        m[s][s] += 1
        d[i] += 1
    l1 = sorted(d.keys())
    total = 0
    ans = l1
    for l in permutations(l1):
        total1 = 0
        for i in range(len(l) - 1):
            s1 = ord(l[i]) - 65
            for j in range(i + 1, len(l)):
                s2 = ord(l[j]) - 65
                total1 += m[s1][s2]
        if total1 > total:
            total = total1
            ans = l
    ans1 = ''
    for i in ans:
        ans1 += i * d[i]
    out(ans1)