# Combinatorics to calculate hamming distance

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.

• Please refrain from asking the same question twice (math.stackexchange.com/questions/1731654/…). This version is better-phrased, but as you know, you can edit questions rather than just creating new versions. Apr 7 '16 at 7:31

## 2 Answers

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.

• 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. Apr 7 '16 at 8:21
• @satya: OK, I'd misunderstood -- I've edited the answer accordingly. Apr 7 '16 at 8:26
• it is still not correct ,look at the example i gave in question. Apr 7 '16 at 9:24
• @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$. Apr 7 '16 at 9:31
• i corrected it now so will your formula work correctly here? Apr 7 '16 at 9:37

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];

}

}
`