cf_rk's blog

Google Online Coding Round 2021 Problem !!!
By cf_rk, history, 5 years ago, In English

You are given a binary string s (consisting of 0's and 1's). Count the number of substrings with count of 1's > count of 0's.

For eg. Input: 1010 Output: 3 Explanation: Possible substring with count of 1's > count of 0's are : {1} , {101} , {1}.

What I did? I converted all 0's to -1. Then the problem reduces to Count number of subarrays with positive sum. Then I used fenwick tree for it and it passed.

Is there any other approach for this. Thanks in advance!

  • Vote: I like it
  • -21
  • Vote: I do not like it

»
5 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

Balanced BST

→ Reply
»
5 years ago, hide # |
 
Vote: I like it -7 Vote: I do not like it

fft

→ Reply
»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Find the number of intervals with sum 0. To do this, find the length of the intervals composed of only 0. The rest is trivial

→ Reply