Leonardo & the SubString - HackrRank Challenge

Leonardo & the SubString:

• In this post we will solve the programming challenge of "Leonardo & the substring" matching posted in HackrRank.

Problem Description:

Leonardo loves puzzles involving strings, but he's just found a problem that has him stumped! Help him solve the following challenge:

Given a binary string, S, composed of only 0's and 1's, find and print the total number of substrings of S which do not contain a 00 or 11.

Input Format

The first line contains an integer, T(the number of test cases). 
The T subsequent lines of test cases each contain a string, S, composed only of 0's and 1's.

Constraints

• 1≤T≤100
• 1≤|S|≤105

Output Format

For each test case, print the total number of substrings of S having no consecutive zeroes or ones (i.e.: not containing 00 or 11).

Sample Input

4
1010
100
0000
11111

Sample Output

10
4
4
5

Explanation

Test Case 0: S0=1010
Our set of substrings ={{1},{0},{1},{0},{10},{01},{10},{101},{010},{1010}} There are 10possible substrings, none of which have consecutive 0's or 1's. Thus, we print 10on a new line.

Test Case 1: S1=100 
Our set of substrings ={{1},{0},{0},{10},{00},{100}} 
There are 6 possible substrings, but 2 of them ({00}and {100}) have consecutive zeroes. Thus, we print the result of 6−2, which is 4, on a new line.

Algorithm:

• The algorithm is explained with the below given example.

Input Binary String	0	0	1	0	1	1	0	0
Index	0	1	2	3	4	5	6	7

1. Assume there are N elements (N=8 in our example) in the given binary string.
2. Start from the index 0 and take a set of 2, 3, ... (N-stepnumber) of elements at a time, where stepnumber = 0, 1, 2.... (N-1). For the first iteration, the stepnumber is assigned to 0 and increments by 1 for each iteration.
3. In each iteration, we will form a set with 2, 3 , ... etc., elements taken from the given input binary string. In each set, search for the sub-string 00 or 11. 
4. If the sub-string match is found, in any one set, we can break that iteration and go for the next iteration. This is because, if the sub-string match is found in a set of taking x elements at a time, then for all the sets with elements higher than 'x' number of elements, we will be having the sub-string match;so we can break that iteration.
5. Proceed the step number 3 & 4 till we reach the stepnumber (N-1).

Algorithm Illustration:

Stepnumber = 0:

• Start from index = 0. Take 2 elements at a time;i.e {0,0}. This set is having the sub-string 00. So all other sets from index 0 [{001},{0010},{00101},{001011},{0010110},{00101100}] will be having the sub-string "00". So we can break that iteration when we find the first sub-string match.

Stepnumber = 1:

• In this iteration, we will start from index 1. For this step, we can have a set with 2, 3, 4, .... (N-stepnumber) of elements. i.e. we can form a set with 2, 3, 4, .. 7 elements.
• First a set with 2 elements {0,1} is taken. This set do not have any sub-string match. We can now take 3 elements at a time {010} and this too do not have any matching sub-string. The set of taking 4 elements({0101}) too do not have the matching sub-string. The first sub-string match occurs when we take the 5 elements at a time; i.e. {01011}. This set has the matching sub-string 11. So, the set of taking 6 elements {010110} & 7 elements {0101100} will be having the matching sub-string of 11. So, we can terminate this iteration after evaluating the set with 5 elements.

This process is continued till the setpnumber is 7.

C Coding:

• Click on the below link for the "C" program to solve the above problem.

Leonardo SubString Matching

Makefile to compile the program