You are not logged in. Please login at to post your questions!


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

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:



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)


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

asked 30 Jan, 08:14

brij_raj's gravatar image

accept rate: 10%

edited 30 Jan, 08:18

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.


answered 30 Jan, 08:33

shashwatchandr's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 30 Jan, 08:14

question was seen: 407 times

last updated: 30 Jan, 08:33