Rotate String to find Hamming distance equal to K

user_16420723 0
Viewed 224

We are given 2 binary strings (A and B) both of length N and an integer K. We need to check if there is a rotation of string B present where hamming distance between A and the rotated string is equal to K. We can just remove one character from front and put it at back in single operation.

Example : Let say we are given these 2 string with values as A="01011" and B="01110" and also K=4.

Note : Hamming distance between binary string is number of bit positions in which two corresponding bits in strings are different.

In above example answer will be "YES" as if we rotate string B once it becomes "11100", which has hamming distance of 4, that is equal to K.

Approach :

For every rotated string of B 
    check that hamming distance with A
    if hamming distance == K:
       return "YES"
return "NO"

But obviously above approach will execute in O(Length of string x Length of string) times. Is there better approach to solve this. As we don't need to find the actual string, I am just wondering there is some better algorithm to get this answer.

Constraints :

Length of each string <= 2000
Number of test cases to run in one file <=600
bit-manipulation algorithm string
1 Answers

First note that we can compute the Hamming distance as the sum of a[i]*(1-b[i]) + b[i]*(1-a[i]) for all i. This simplifies to a[i] + b[i] - 2*a[i]*b[i]. Now in O(n) we can compute the sum of a[i] and b[i] for all i, and this doesn't change with bit rotations, so the only interesting term is 2*a[i]*b[i]. We can compute this term efficiently for all bit rotations by noting that it is equivalent to a circular convolution of a and b. We can efficiently compute such convolutions using the Discrete Fourier transform in O(n log n) time.

For example in Python using numpy:

import numpy as np

def hdist(a, b):
    return sum(bool(ai) ^ bool(bi) for ai, bi in zip(a, b))
def slow_circular_hdist(a, b):
    return [hdist(a, b[i:] + b[:i]) for i in range(len(b))]
def circular_convolution(a, b):
    return np.real(np.fft.ifft(np.fft.fft(a)*np.fft.fft(b[::-1])))[::-1]
def fast_circular_hdist(a, b):
    hdist = np.sum(a) + np.sum(b) - 2*circular_convolution(a, b)
    return list(np.rint(hdist).astype(int))

Usage:

>>> a = [0, 1, 0, 1, 1]
>>> b = [0, 1, 1, 1, 0]
>>> slow_circular_hdist(a, b)
[2, 4, 2, 2, 2]
>>> fast_circular_hdist(a, b)
[2, 4, 2, 2, 2]

Speed and large correctness test:

>>> x = list((np.random.random(5000) < 0.5).astype(int))
>>> y = list((np.random.random(5000) < 0.5).astype(int))
>>> s = time.time(); slow_circular_hdist(x, y); print(time.time() - s)
6.682933807373047
>>> s = time.time(); fast_circular_hdist(x, y); print(time.time() - s)
0.008500814437866211
>>> slow_circular_hdist(x, y) == fast_circular_hdist(x, y)
True
user_5656350
Related