requirements

Given a string s, count the number of non-empty (continuous) substrings with the same number of zeros and ones, and all zeros and all ones in those substrings are continuous.

Repeated substrings count the number of times they occur.

Example 1:

Input: "00110011" Output: 6 Description: There are six substrings with the same number of consecutive 1s and 0s: "0011 ", "01", "1100", "10", "0011 "and" 01 ". Note that some repeated substrings count their occurrences. Also, "00110011" is not a valid substring because all zeros (and ones) are not combined.Copy the code

Example 2:

Input: "10101" Output: 4 Explanation: There are four substrings: "10 ", "01", "10", "01", which have the same number of consecutive ones and zeros.Copy the code

Tip:

  • S. length is between 1 and 50,000.
  • The s contains only 0 or 1 characters.

The core code

class Solution:
    def countBinarySubstrings(self, s: str) - >int:
        count = 0
        for i in range(len(s) - 1):
            left,right = s[i],s[i + 1]
            left_idx,right_idx = i,i + 1
            ifleft ! = right:while 0 <= left_idx <= right_idx < len(s) and s[left_idx] == left and s[right_idx] == right:
                    count += 1
                    left_idx,right_idx = left_idx - 1,right_idx + 1
        return count 
Copy the code

We use a slider of length 2 to traverse the entire string, and when we hit left! = rihgt, we expand left and right in the current window. If the left and left are the same, and the right and right are the same, then we can constantly get substrings. It is a good idea and worth learning from.