Lexicographically Small Enough (Codeforces 1616E)
Tags: Greedy, strings

You are given two strings $$$s$$$ and $$$t$$$ of equal length $$$n$$$. In one move, you can swap any two adjacent characters of the string $$$s$$$.You need to find the minimal number of operations you need to make string $$$s$$$ lexicographically smaller than string $$$t$$$.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: The first line of input contains one integer $$$q$$$ ($$$1 \le q \le 10\,000$$$): the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).The second line of each test case contains the string $$$s$$$ consisting of $$$n$$$ lowercase English letters.The third line of each test case contains the string $$$t$$$ consisting of $$$n$$$ lowercase English letters.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print in a separate line the minimal number of operations you need to make string $$$s$$$ lexicographically smaller than string $$$t$$$, or $$$-1$$$, if it's impossible.


Sample Inputs:
4
1
a
a
3
rll
rrr
3
caa
aca
5
ababa
aabba

Sample Outputs:
-1
0
2
2

Solution (Python):
""""""
import abc
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.write
DEBUG = os.environ.get('debug') is not None
if DEBUG:
    from inspect import currentframe, getframeinfo
    from re import search

def debug(*args):
    if not DEBUG:
        return
    frame = currentframe().f_back
    s = getframeinfo(frame).code_context[0]
    r = search('\\((.*)\\)', s).group(1)
    vnames = r.split(', ')
    var_and_vals = [f'{var}={val}' for (var, val) in zip(vnames, args)]
    prefix = f'{currentframe().f_back.f_lineno:02d}: '
    print(f"{prefix}{', '.join(var_and_vals)}")
INF = float('inf')

class FenwickTreeSum:

    def __init__(self, N, nums=[]):
        """"""
        self.N = N
        self.tree = [0] * (N + 1)
        for (i, num) in enumerate(nums):
            self.update(i + 1, num)

    def query(self, i):
        """"""
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def update(self, i, val):
        """"""
        while i <= self.N:
            self.tree[i] += val
            i += i & -i

def solve(N, S, T):
    S = [ord(c) - ord('a') for c in S]
    T = [ord(c) - ord('a') for c in T]
    avail = [[] for _ in range(26)]
    for i in range(N - 1, -1, -1):
        avail[S[i]].append(i)
    fw = FenwickTreeSum(N)
    res = INF
    pref = 0
    for (i, t) in enumerate(T):
        cur = INF
        for c in range(t):
            if not avail[c]:
                continue
            j = avail[c][-1]
            d = fw.query(j)
            cur = min(cur, j - d)
        res = min(res, pref + cur)
        if not avail[t]:
            break
        j = avail[t].pop()
        d = fw.query(j)
        pref += j - d
        fw.update(j + 1, 1)
    return res if res < INF else -1

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        S = input().decode().strip()
        T = input().decode().strip()
        out = solve(N, S, T)
        output(f'{out}\n')
if __name__ == '__main__':
    main()

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

class fenwick(object):

    def __init__(self, n):
        self.n = n
        self.cul = [0] * n

    def update(self, index, diff):
        i = index
        while i < self.n:
            self.cul[i] += diff
            i += i + 1 & -i - 1

    def getaccu(self, index):
        output = 0
        i = index
        while i >= 0:
            output += self.cul[i]
            i -= i + 1 & -i - 1
        return output

def main(t):
    n = int(input())
    s1 = input().decode('utf-8')
    s2 = input().decode('utf-8')
    indexes = [[] for _ in range(26)]
    for i in range(n):
        indexes[ord(s1[i]) - 97].append(i)
    for k in range(26):
        indexes[k] = indexes[k][::-1]
    fen = fenwick(n)
    ans = float('inf')
    base = 0
    for i in range(n):
        num = n + 3
        for c in range(ord(s2[i]) - 97):
            if indexes[c]:
                num = min(num, indexes[c][-1])
        if num < n + 3:
            temp = base + num - fen.getaccu(num)
            ans = min(temp, ans)
        if not indexes[ord(s2[i]) - 97]:
            break
        num = indexes[ord(s2[i]) - 97].pop()
        base += num - fen.getaccu(num)
        fen.update(num, 1)
    if ans == float('inf'):
        print(-1)
    else:
        print(ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
import sys

def solve():
    inp = sys.stdin.readline
    n = int(inp())
    s = inp().strip()
    A = ord('a')
    pos = [[] for i in range(26)]
    for i in range(n):
        pos[ord(s[i]) - A].append(i)
    for i in range(26):
        pos[i].reverse()
    t = inp().strip()
    F = [0] * n
    res = 10 ** 20
    now = 0
    for i in range(n):
        best_pos = n + 10
        best = -1
        for j in range(ord(t[i]) - A):
            v = pos[j]
            if v and best_pos > v[-1]:
                best = j
                best_pos = v[-1]
        if best != -1:
            v = pos[best]
            if v:
                p = v[-1]
                z = 0
                x = p
                while x >= 0:
                    z += F[x]
                    x = (x & x + 1) - 1
                res = min(res, now + p - z)
        v = pos[ord(t[i]) - A]
        if not v:
            break
        p = v[-1]
        v.pop()
        z = 0
        x = p
        while x >= 0:
            z += F[x]
            x = (x & x + 1) - 1
        now += p - z
        x = p
        while x < n:
            F[x] += 1
            x |= x + 1
    if res >= 10 ** 20:
        print(-1)
    else:
        print(res)

def main():
    for i in range(int(sys.stdin.readline())):
        solve()
if __name__ == '__main__':
    main()