Problem statement

https://binarysearch.com/problems/Minimum-Adjacent-Swaps-to-Palindrome/

Solution 1

The idea is to greedy construct palindrome, symbol by symbol, using two pointers technique. Imagine that we have abc...cdeba. Then for the first two symbols they are already on place. For symbol c, we start form the -3 symbol and look for symbol c. When we found it, we do swaps. So, we have abc...dceba -> abc...decba. Then we proceed in similar way.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def solve(self, s):
        if sum(x % 2 == 1 for x in Counter(s).values()) > 1: return -1

        l, r, s = 0, len(s) - 1, list(s)
        ans = 0
        while l < r:
            if s[l] != s[r]:
                k = r
                while k > l and s[k] != s[l]:
                    k -= 1
                if k == l:
                    ans += 1
                    s[l], s[l + 1] = s[l + 1], s[l]
                else:
                    while k < r:
                        s[k], s[k + 1] = s[k + 1], s[k]
                        k += 1
                        ans += 1
                    l, r = l + 1, r - 1
            else:
                l, r = l + 1, r - 1
        return ans

Solution 2 (advanced)

There is also O(n log n) solution, using BIT, similar idea to CF1616E. The idea is to create P first: are pairs of indexes for each letter. Imagine, that we have a on positions 0, 4, 9, 11, then we create pairs [0, 11], [4, 9]. Then we sort these pairs, because we want to proceed them from left to right.

This solution is inspired by user TheScrasse from CodeForces, here is his more detailed explanation:

Since it’s useless to swap equal characters, you know which pairs of characters will stay on symmetrical positions in the final string, i.e. the i-th leftmost occurrence and the i-th rightmost occurrence of any character c. In the string acabcaaababbc, for example, you can make these “symmetrical pairs”: positions (1, 10), (2, 13), (3, 8), (4, 12), (6, 7), (9, 11). The character in position 5 should go in the center of the final string (i.e. position 7). The symmetrical pairs have to be nested inside each other, in some order. Given two symmetrical pairs, which of them should be located outside the other one? It turns out that the pair that contains the leftmost element should be located outside. In fact, if you want to reach xyyx, the initial configurations with x on the left (xxyy, xyxy, xyyx) require 2, 1, 0 moves respectively, while reaching yxxy requires 2, 1, 2 moves respectively. So you can sort the symmetrical pairs by leftmost element and construct the array a such that ai is the final position of si in the palindromic string (in this case, [1, 2, 3, 4, 7, 5, 9, 11, 6, 13, 8, 10, 12]) and the result is the number of inversions of a.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class BIT:
    def __init__(self, n):
        self.sums = [0] * (n+1)
    
    def update(self, i, delta):
        while i < len(self.sums):
            self.sums[i] += delta
            i += i & (-i)
    
    def query(self, i):
        res = 0
        while i > 0:
            res += self.sums[i]
            i -= i & (-i)
        return res

class Solution:
    def solve(self, s):
        n = len(s)
        s = [ord(x) - 95 for x in s]
        ans, bit = 0, BIT(n)
        if sum(x % 2 == 1 for x in Counter(s).values()) > 1: return -1

        idx = defaultdict(list)
        for i, c in enumerate(s):
            idx[c].append(i)

        B, P = [0] * n, []
        for c, I in idx.items():
            cnt = len(I)
            if cnt % 2:
                B[I[cnt//2]] = n//2 + 1
            for i in range((cnt)//2):
                P += [(I[i], I[~i])]

        for i, (l, r) in enumerate(sorted(P)):
            B[l], B[r] = i + 1, n - i
        
        for i, b in enumerate(B):
            ans += i - bit.query(b)
            bit.update(b, 1)
        
        return ans