LensKart Hiring : Find length of largest substring of a binary String in which frequency of set bits < frequency of reset bits

general
, , ,
1

Given a binary string of length N, find the length of longest substring in which number of 0’s > number of 1’s.

1 \leq N \leq 10^{5}

Example Input:

6 \\011100

Eample Output:

3

Explaination:

The largest 3 characters 100 forms a substring of length 3 in which number of 0’s > no. of 1’s.

My approach :

I have converted this question in different way. I have changes all 0’s to 1 and all 1’s to -1 and store the individual digits 1 and -1 in an 1d integer array. Then the task reduced to Longest Subarray with Sum greater than Equal to Zero GeeksforGeeks with a modification that sum should be positive. Is my approach correct? I have taken the code of geeksforgeeks and modified a line in the binary search

if (searchspace[mid] - key >= 0)

to

if (searchspace[mid] - key > 0)

I cannot check whether I am wrong or right by submitting as it was of hiring challenge and now the questions are not available. But Is there any other approach it can be solved? This question was asked in Lenskart Hiring Challenge

2

After converting the all the 1s to -1 and the 0s to 1 , For each R , you need the smallest L such that pref[R]-pref[L-1] > 0 -> pref[R] > pref[L-1] for this you can keep a segment tree on the value of pref[i] so each node stores the minimum index which has value in the nodes range. To get the answer for each R, you query the min from -N to Pref[R]-1.