旭的小窝

696. Count Binary Substrings

 
  • 2023年 06月14日

Promble

link: https://leetcode.com/problems/count-binary-substrings/description/

Given 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.

Input: s = "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.

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

Approach 1

groups the s

Thought

  1. first group the s to the groups
    1. 001100111 > groups = [2,2,2,3]
  2. def ans to store the final result.
  3. point:
    1. Let’s try to count the number of valid binary strings between groups[i] and groups[i+1]. If we have groups[i] = 2, groups[i+1] = 3, then it represents either “00111” or “11000”. We clearly can make min(groups[i], groups[i+1]) valid binary strings within this string. Because the binary digits to the left or right of this string must change at the boundary, our answer can never be larger.
  4. loop i in range(1, len(groups))
    1. ans += min(groups[i-1], groups[i])
  5. return ans

Code

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        groups = [1]
        # calc the groups of different number
        for i in range(1, len(s)):
            if s[i-1] != s[i]:
                groups.append(1)
            else:
                groups[-1] += 1

        ans = 0 
        for i in range(1, len(groups)):
            ans += min(groups[i-1], groups[i])
        return ans

Approach 2

use itertools lib. (like Approach 1 method.)

Thought

  1. use itertools.groupby to group the s > ‘001100111’ to [2,2,2,3]
  2. def ans += min(group[i], group[i-1])
  3. return ans

Code

import itertools 

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        groups = [len(list(v)) for _, v in itertools.groupby(s)]
        
        return sum(min(a, b) for a,b in zip(groups, groups[1:]))

Approach 3

linear scan

Thought

  1. only remember only prev = groups[-2] and cur = groups[-1].
  2. the answer is the sum of min(prev, cur) over each different final (prev, cur).

Code

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        ans, prev, cur = 0, 0, 1
        for i in range(1, len(s)):
            if s[i-1] != s[i]:
                ans += min(prev, cur)
                prev, cur = cur, 1
            else:
                cur += 1 

        return ans + min(prev, cur)
搜索