JS - Leetcode-01

Question

Count Binary Substrings:
Give a binary string s, return the number of non-empty substrings that have:
- the same number of 0's and 1's,
- and all the 0's and all the 1's in these substrings are grouped consecutively.
Substrings that occur multiple times are counted the number of times they occur.

Example

Explanation:
- "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.
- But within "00110011", there are 6 valid consectuive substrings: "0011", "01", "1100", "10", "0011", and "01"
- "00001111" then is a valid substring

Solution

O(n) time complexity Solution:
const countBinarySubstrings = (s) => {
  let curr = 1;
  let prev = 0;
  let ans = 0;
  for (let i = 1; i < s.length; i++) {
    if (s[i] === s[i - 1]) {
      // find the location of each "01" point
      curr++;
    } else {
      /*
      check min(numOfZeros, numOfOnes)
      "01" = 1 ans
      "0011" = 2 ans - "01" and "0011"
      "000111" = 3 ans = "01", "0011" and "000111"
      */
      ans += Math.min(curr, prev);
      prev = curr;
      curr = 1;
    }
  }
  return ans + Math.min(curr, prev);
};
console.log(countBinarySubstrings('00110011'));