title: Optimize getting all sub-strings of a binary string
body: <p>The code is to convert a decimal number to binary, generate all possible sub-strings of the binary string and calculate the odd number of 0's and 1's in each of the sub-string and finally return the total count. Running this code gives timeout error in sites like hackerrank. What approach should be used to reduce the complexity here? I tried pushing all the binary numbers in an array &amp; then iterating it separately to avoid 0(n^3). But even that doesn't seem to work. Should a dynamic programming approach be taken here?</p>
  
  <p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
  <div class="snippet-code">
  <pre class="snippet-code-js lang-js prettyprint-override"><code>    function getAllSubstrings(str) {
    let result = [];
    let n = str.length
    let oddZeroCnt = 0;
    let oddOneCnt = 0;
    for (let i = 0; i &lt; n; i++)
      for (let j = i + 1; j &lt;= n; j++) {
        let substr = str.substring(i, j);
        let zeroSubStr = (substr.split("0").length - 1)
        let oneSubStr = (substr.split("1").length - 1)
        if (zeroSubStr % 2 === 1) {
          oddZeroCnt++
        }
        if (oneSubStr % 2 === 1) {
          oddOneCnt++
        }
      }
    return oddZeroCnt + " " + oddOneCnt;
  }
  
  function getOddCounts(decNum) {
    return getAllSubstrings((decNum &gt;&gt; BigInt(0)).toString(2))
  }
  let input = BigInt(17)
  console.log(getOddCounts(input))</code></pre>
  </div>
  </div>
  </p>