Count Binary Substrings

Problem by Leetcode: https://leetcode.com/problems/count-binary-substrings/description/

Give a string s, count the number of non-empty (contiguous) 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 1:

Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".

Notice that some of these substrings repeat and are counted the number of times they occur.

Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

Example 2:

Input: "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

Note:

s.length will be between 1 and 50,000.

s will only consist of "0" or "1" characters.

With the length of the string in the 50K range, any N^2 solution will be intractable. There is a way to solve this problem in O(n)-time and O(1)-space:

• With 2 variables you'll keep track of the number of consecutive ones, and the number of consecutive zeros, one variable for each
• Make sure to reset the count exactly when you transition from one to the other
• Every time that you increment either the consecutive ones, or the consecutive zeros, you check whether that count is still less than or equal than the other one. The idea is that if the current count (say for the '1's) is still less than the other count (say for the '0's), it means that you have found a new substring matching the criteria. Then, increment the return value

That's it. Code is below, cheers, Marcelo.

public class Solution
{
 public int CountBinarySubstrings(string s)
 {
  if (String.IsNullOrEmpty(s)) return 0;

  int numberConsecutiveOnes = 0;
  int numberConsecutiveZeroes = 0;
  int result = 0;

  for (int i = 0; i < s.Length; i++)
  {
   if (s[i] == '0')
   {
    if (i - 1 >= 0 && s[i - 1] == '1') numberConsecutiveZeroes = 0;
    numberConsecutiveZeroes++;
    if (numberConsecutiveZeroes <= numberConsecutiveOnes) result++;
   }
   else
   {
    if (i - 1 >= 0 && s[i - 1] == '0') numberConsecutiveOnes = 0;
    numberConsecutiveOnes++;
    if (numberConsecutiveOnes <= numberConsecutiveZeroes) result++;
   }
  }

  return result;
 }
}