title: Given a string which contains only ones and zeros, return the number of substrings with ones more than zeros
body: <p>Suppose that S is a string containing only 0 and 1. I would like to count the number of not null substrings of S in which the number of 0s is less than the number of 1s.</p>
  <p>Using brute-force method given below we can have an algorithm that solves this problem in O(n^2):</p>
  <pre><code>moreOnes(s):
  count = 0
  n = s.len()
  
  for i = 1 to n
      one = 0
      zero = 0
      for j = i to n
          if s[i] == '1'
              one++
          else
              zero++
          
          if one &gt; zero
              count++
  
  return count
  </code></pre>
  <p>But can we have an algorithm with a better time complexity of O(n*logn) or O(n), and space complexity be anything from O(1) to O(n)?</p>