Problem statement

https://leetcode.com/problems/k-similar-strings/

Solution

Note similarity of this problem with Problem 0765 Couples Holding Hands, but here we have more $6$ different symbols. Let us look at this problem as to graph: for example if we have A = abcde and B = bcaed, then we need to find $2$ loops: $a\to b\to c\to a$ and $d\to e\to d$. In general we need to find minimum number of loops in directed graph on $m = 6$ nodes, where we can have multiple edges and we have $n$ edges. However it is still difficult problem and it is not obvious how to handle it.

Let us assign number to each letter: a:1, b:32, c:$32^2$, $d:32^3$, e:$32^4$, f:$32^5$. Now, we evaluate difference between corresponding elements of two strings, so for example for given example we have [-31, -992, 1023, -1015808, 1015808]. Now, finding loop is equivalent to group of elements which has $0$ when we sum them! Why? Because if some sum is equal to zero, it means, that numbers in both sets are equal:we choose $32$ > $20$, length of our string): indeed, imagine, that we have set of numbers with sum $0$, it means: \(\alpha_0 \cdot 1 + \alpha_1\cdot 32 + \dots + \alpha_5\cdot 32^5 = \beta_0 \cdot 1 + \beta\cdot 32 + \dots + \beta\cdot 32^5,\) where $\alpha_0, \dots, \alpha_5$ is corresponding number of a, b, c, d, e, f, similar for betas. From here we have \(\gamma_0 \cdot 1 + \gamma_1\cdot 32 + \dots + \gamma_5\cdot 32^5 = 0,\) where $\gamma_i = \alpha_i - \beta_i \in [-20, 20]$. If we consider not biggest $\gamma_i$ which is not equal to $0$, then sum of all other terms is smaller than this term, so it means that all $\gamma_i$ equal to zero, that is we have the same set of letters.

Actually, this is almost equivalent to Problem 0465 Optimal Account Balancing Optimal Account Balancing, and to Problem 0698 Partition to K Equal Sum Subsets.

Complexity

Time complexity is $O(2^n\cdot n)$ and space complexity is $O(2^n)$.

To be accepted on Leetcode, we need to make couple of optimizations: first of all, if two symbols on the same place are equal, we just remove them. Also if we have loop of length $2$ we also remove it: here I use trick, where we intersect count for nums and list with all opposite numbers from nums. Then for each element we repeat it as much times as needed and delete from our list.

Code

class Solution:
    def kSimilarity(self, A, B):
        nums = [((1<<ord(i)*5) - (1<<ord(j)*5))>>(97*5) for i,j in zip(A,B) if i!=j] 

        Cnt = Counter(nums) & Counter(-n for n in nums)
        pairs = list(chain(*([i]*j for i, j in Cnt.items())))
        for num in pairs: nums.remove(num)
        
        n = len(nums)
        
        dp = [(-1,0)] * (1<<n)
        dp[0] = (0, 0)

        for mask in range(1<<n):
            for j in range(n):
                if mask & (1<<j):
                    steps, summ = dp[mask ^ (1<<j)]
                    dp[mask] = max(dp[mask], (steps + (summ==0), summ + nums[j]))

        return n - dp[-1][0] + len(pairs)//2