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.
 A: 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.
A: 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];

       }

     }

