1
$\begingroup$

We have a string S of length L comprising of alphabets between a to z. We write all strings of length L formed by taking just alphabets a and b. If L=3 we can form aaa aba bba etc. If L is 2 we can form ab ba bb and aa .Is there any combinatorics method to find all strings such that hamming distance between S and all letters formed of length L by using a and b is K where k is less than L. Hamming distance is the number of positions at which characters are different in two strings. If string A is AAB and string B is AAC then hamming distance between string A and B is 1. For clarity of question, We form all possible new strings comprising of letter a and b and of length L and out of those strings we choose the ones whose hamming distance with string S is K. If L=5 then there are 2^5 possible strings and out of those we need to check if hamming distance between S and them is equal to k.

let the string be abc.

if we look at all posiible strings of lenth 3 formed by just a nd b are

strings > hamming distance

aba- 1

aab 2

baa 3

bba 2

bab 3

bbb 2

aaa 2

abb 1

so ans is 4 if k=2 ,ans is 2 if k=3.

$\endgroup$
1
$\begingroup$

Let the string $S$ have $m$ letters that are either 'a' or 'b' and $n$ that aren't. If $n\gt k$, there are no admissible strings, since the Hamming distance is at least $n$. If $n\le k$, we can choose any $k-n$ of the $m$ letters to flip from 'a' to 'b' or vice versa, and for the $n$ letters that aren't 'a' or 'b' we can freely choose either 'a' or 'b'. Thus there are

$$ 2^n\binom m{k-n} $$

such strings.

$\endgroup$
  • $\begingroup$ We form all possible new strings comprising of letter a and b and of length L and out of those strings we choose the ones whose hamming distance with string S is K. If L=5 then there are 2^5 possible strings and out of those we need to check if hamming distance between S and them is equal to k. $\endgroup$ – satyajeet jha Apr 7 '16 at 8:21
  • $\begingroup$ @satya: OK, I'd misunderstood -- I've edited the answer accordingly. $\endgroup$ – joriki Apr 7 '16 at 8:26
  • $\begingroup$ it is still not correct ,look at the example i gave in question. $\endgroup$ – satyajeet jha Apr 7 '16 at 9:24
  • 1
    $\begingroup$ @satya: You miscounted in the example. Two strings that begin with 'a' are listed with Hamming distance $3$ despite coinciding with the given string on the intial 'a'. Also, the last string abb has Hamming distance $1$ from abc, not $2$. $\endgroup$ – joriki Apr 7 '16 at 9:31
  • $\begingroup$ i corrected it now so will your formula work correctly here? $\endgroup$ – satyajeet jha Apr 7 '16 at 9:37
0
$\begingroup$

I dont know the mathematical formula but this simple DP recurrence will do the trick for you.

dp[i][j] == number of prefixes of length i have hamming distance of j

1) if the last character we add is same as given string , then dp[i][j] += dp[i-1][j]

2) if the last character we added is not similar to given string then dp[i][j] += dp[i-1][j-1]*(A-1) where A is the number of possible
characters allowed.

Therefore dp[i][j] = dp[i-1][j-1]*(A-1) + dp[i-1][j] .

Therefore final answer will be sum of dp[n][0] + dp[n][1] +.....+ dp[n][k]

Hope this resolves your query :)

Here is the code - snippet `

 dp[0][0] = 1 ;
   dp[0][1] =  A   - 1 ;

  for( int i = 0 ; i < n ; i ++ )
   {
   for( int j= 0 ; j < n ; j ++ )
      {

        if(  i-1 >= 0 && j-1>=0)
         dp[i][j]+=dp[i-1][j-1]*(A - 1);

        if(  i-1 >= 0 && j>=0)
            dp[i][j]+=dp[i-1][j];

       }

     }
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.