Python: Given 2 binary strings s and t, print minimum number of adjacent swaps to convert s to t

Question

For example if s = "1000000111" and t = "0111000001" the output should be 11. Below is my solution but it gives a time limit exceeded error so I am looking for a faster method. The length of string is less than 10^6.

T = int(input())
for _ in range(0,T):
    n = int(input())
    s = input()
    source = []
    for letter in s:
        source.append(letter)
    #source[0],source[1] = source[1],source[0]
    #print(source)
    t = input()
    target = []
    for letter in t:
        target.append(letter)
    if source.count("1") != target.count("1") or source.count("0") != target.count("0"):
        print(-1)
        continue
    else:
        ans = 0
        for i in range(0,n):
            if source[i] != target[i]:
                #print("".join(source),"".join(target))
                if source[i] == "0":
                    j = i
                    while source[j] != "1":
                        j += 1
                    ans += j-i
                    source[i],source[j] = source[j],source[i]
                else:
                    #print(source)
                    j = i
                    while source[j] != "0":
                        #print(j,ans)
                        j+=1
                    ans += j-i
                    source[i],source[j] = source[j],source[i]
        print(ans)

score 3 · Accepted Answer · answered Jul 11 '20 at 17:48

Here's the code. The idea is that you count the location of '1's and then calculate the difference between the pairs. Time complexity O(n), space complexity O(n), but can be done O(1) with a careful indexing.

def foo(str1, str2):
        if len(str1) != len(str2):
            return -1
        n = len(str1)
        
        arr1 = [i for i in range(n) if str1[i] == '1']
        arr2 = [i for i in range(n) if str2[i] == '1']
        
        if len(arr1) != len(arr2):
            return -1
        
        res = 0
        for i in range(len(arr1)):
            res += abs(arr1[i] - arr2[i])
        return res

Python: Given 2 binary strings s and t, print minimum number of adjacent swaps to convert s to t

1 Answers1