Number of Substrings JPMC

The question appeared in the coding test taken by JP Morgan Chase in one of the placement drives.

Task :- Given a string of 0s and 1s, find the number of substrings that match the following conditions :

• The number of 1s and 0s in the substring are equal.
• The 1s and 0s are clubbed together.

Note: Two substrings are different if their starting or ending index is different.

For eg: str = “ 0011001 ”

The substrings that satisfy both the conditions are “0011”,”01”,”1100”,”10”,”01”. So the answer is 5.

The substring “1001” satisfies the first condition but the 1s and 0s are not clubbed together.

Brute force Approach :- We can use two for loops to traverse the string. The outer for loop goes from index 0 to n-1, where n is the length of string. The inner for loop goes from i to n-1 and checks whether the substring starting with index i and ending with index j satisfies both the conditions or not. If it does we increment a variable which stores count of such substrings.

We can create two separate functions to check each condition if both of them return True that means the substring is a valid substring.

The first function maintains count of 0s and 1s in the string. If count of 0s is the same as count of 1s then we return true else we return false.

Note that a substring with odd length cannot satisfy the first condition. Hence we can directly return false for that condition.

The second function goes from index 0 to m/2 and checks whether the elements are the same and then checks whether the elements from index ( m/2 +1) to m-1 are all the same. If they are the same then we return true else we return false.

m → len(substring)

The time complexity of this approach is O( N² ) and is not enough to solve all the test cases.

Brute Force Code :-

Efficient approach :- We can observe that for a substring consisting of ‘x’ continuous 1s and ‘y’ continuous 0s the substrings that satisfy both the conditions is given by min(x, y).

For eg: string = “…0000111….”

The substrings valid are “000111”,”0011”,”01”.

No of substrings = 3 = min(4,3) = min( no of adjacent 1s, no of adjacent 0s).

For a string consisting of multiple such inversions from 0s to 1s or vice versa, the final answer would be the sum of all such inversions.

For the first example string = “ 0011001 ”

First there are 2 zeros, then 2 ones, then 2 zeros, then 1 one.

So we can get an array = [ 2, 2, 2, 1 ]

Answer = Summation of min ( adjacent elements )

= min(2,2) + min(2,2) + min(2,1)

= 2 + 2 + 1

= 5

The time complexity of this approach is linear i.e- O(N) since we are traversing the string once and then the array once which can be of maximum N length. So the overall time complexity remains O(N).

Code:-