# Number of unique substrings of particular length of a binary string

Question: A binary string is given with only 0's and 1's. A number n is also given as the length of a sub string to be considered. It is to find the number of unique substrings. Here, n=3.

My algorithm: The ways I followed: (i) First, I extracted out the sub string of length 3 and converted it into a number. (ii) Then, I stored the number in a new integer type array. In this way, I had an integer array full of numbers representing the substrings. (iii) Lastly, I traversed down the array, keeping track of the occurrence of the unique numbers only. The amount of unique numbers therefore correspond to the number of unique substring.

#include<stdio.h>
#include <string.h>

int main(void)
{
char arr[50];
int o[50],check[10000];
int i,j,count=1,l,k=0,sum,p;

l=strlen(arr);

for(i=0;i<l-2;i++){
p=4;sum=0;
for(j=0;j<3;j++){
sum+=(arr[i+j]-'0')*p;
p/=2;
}
o[k++]=sum;
}

memset(check,0,sizeof(check));

for(i=0;i<k-1;i++){
for(j=i+1;j<k;j++){
if(o[i]!=o[j] && check[o[i]]!=1 && check[o[j]]!=1){
count++;
check[o[j]]=1;
}
}
check[o[i]]=1;
}

printf("\n%d",count);

return 0;
}


I think that my code is quite long and it could be shortened with a good optimization. But I can't think of a way.

• How big the string, how vast be n? – Deduplicator Nov 18 '19 at 19:35
• @chux I've edited the question... – Nehal Samee Nov 19 '19 at 11:19
• @chux sorry for the discomfort...I've considered n=3 here...I've cleared the question... – Nehal Samee Nov 19 '19 at 16:21

Your code can be more efficient. For example, both nested for-loops can be replaced with single for-loops. In the first loop, the next sum can be calculated by left-shifting the previous sum, adding the new bit, and masking off n-bits. count[sum] is how many times an n-bit pattern == sum has been seen. So the second loop merely counts how many '1's are in count. Something like the code below (not tested).

int count_unique(char *arr, int n) {
int mask = (1 << n) - 1;

/* the size needs to be 2**n.  This works for n <= 10 */
int count[1024];
memset(count, 0, sizeof(count));

int sum = 0;

for (int i = 0; arr[i]; i++) {
sum = ((sum << 1) | (arr[i] - '0')) & mask;

if (i >= n - 1) {
count[sum]++;
}
}

int unique = 0;

for (int i = 0; i < sizeof(count)/sizeof(int); i++) {
if (count[i] == 1) {
unique++;
}
}

return unique;
}