A reader asked if I could help him with the Square Subsequences problem on HackerRank.

Basically you need to generate all subsequences of a given string (i.e., a powerset of the set of chars), count the number of subsequences that are square, and return this count.

In the past I have already coded a powerset algorithm that generates all subsets for a given set of integers, from 1 to n. However in this case we have a given string, so we can’t use that same algorithm.

The solution I tried involved using the growth of a binary number to select the right chars and form all subsequences (basically you include the chars where the respective binary digit is 1).

For instance, if the string is ‘abcd’, I started with the binary number 1000, meaning the current subsequence is only ‘a’. Then I increased the binary number by 1 to 1001, meaning now the subsequence is ‘ad’. Then the number increased to 1010, meaning the subsequence is ‘ac’. If you keep increasing the number eventually you get all the subsequences of that length. Then you need to start with ‘bcd’.

It worked for 2 out of 7 test cases, timing out on the failed ones.

In other words, the solution below should be correct, but it’s not fast enough. When I have some time I’ll try to speed it up to pass on all test cases.

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

/*function to verify if string is square*/
int isSquare(char buf[]){
        int len;
        char str1[101],str2[101];

        len = strlen(buf);

        /*if string has odd chars it can't be square*/
        if(len%2==1)
                return 0;

        /*separate string in half*/
        strncpy(str1,buf,len/2);
        str1[len/2] = '\0';
        strncpy(str2,buf+len/2,len/2);
        str2[len/2] = '\0';

        /*compare and return result*/
        if(strcmp(str1,str2)==0)
                return 1;
        else
                return 0;
}

/*function to add 1 to the binary number*/
void addBinary(int binary[], int size){
        int i;
        int go = 0;

        for(i=size-1;i>=0;i--){
                if(i==size-1){
                        if(binary[i]==0)
                                binary[i] = 1;
                        else{
                                binary[i] = 0;
                                go = 1;
                        }
                }
                else{
                        if(go==1){
                                if(binary[i]==0){
                                        binary[i] = 1;
                                        go = 0;
                                }
                                else{
                                        binary[i] = 0;
                                        go = 1;
                                }
                        }
                }
        }
        return;
}

/*function that generates all subsequences and tests them, returning total count*/
int countSquareSubsequences(char s[]){
        int len;
        int i,j,k;
        int binary[100]; /*support array that mimics a binary number*/
        char buffer[101]; /*buffer where we transfer the subsequence*/
        int size; /*how many chars are we considering on current cycle*/
        int count = 0;

        len = strlen(s);

        /*iterate starting on each char of the string*/
        for(i=0;i<len;i++){
                size = len - i;
                /*set leftmost digit equal to 1, rest equal to 0*/
                for(j=0;j<100;j++)
                        binary[j]=0;
                binary[0] = 1;

                /*when binary[0]==0 means we are done with this subset of chars*/
                while(binary[0] == 1){
                        k = 0;

                        /*transfer chars to buffer*/
                        for(j=0;j<size;j++){
                                if(binary[j]==1){
                                        buffer[k] = s[i+j];
                                        k++;
                                }
                        }

                        buffer[k] = '\0';
                        if(isSquare(buffer))
                                count++;

                        addBinary(binary,size);
                }
        }

        return count;
}

int main(){
        int t;
        char buffer[201];
        scanf("%d",&t);

        while(t--){
                scanf("%s",buffer);
                printf("%d\n",countSquareSubsequences(buffer));
        }

        return 0;
}