Count Binary Substrings

🏠 ⬅️ ➡️

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.

Example 1:

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.

Example 2:

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.

Constraints:

  • 1 <= s.length <= 105
  • s[i] is either '0' or '1'.
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: i, j, k, n, m, count
    character(len=1000) :: s

    ! read input
    read(*,*) s

    ! find the number of non-empty substrings
    n = len_trim(s)
    do i = 1, n - 1
        if (s(i:i+1) == '00' .or. s(i:i+1) == '11') then
            count = count + 1
        end if
    end do

    ! find the number of substrings with all 0's and all 1's
    m = 0
    do i = 1, n - 1
        if (s(i:i+1) == '00' .or. s(i:i+1) == '11') then
            m = m + 1
        else
            exit
        end if
    end do

    write(*,*) count, m

end program main
✅ Compiled
❌ Executed
❌ Correct 
! Declare variables
integer :: i, j, k, count
character(len=1000000) :: s

! Read input
read(*,*) s

! Initialize variables
i = 1
j = 1
k = 1
count = 0

! Loop through the string
do while (i <= len(s))
    ! Check if the current character is a 0 or a 1
    if (s(i:i) == '0') then
        ! If the current character is a 0, increment the number of 0's
        k = k + 1
    else if (s(i:i) == '1') then
        ! If the current character is a 1, increment the number of 1's
        j = j + 1
    end if

    ! Check if the current substring has the same number of 0's and 1's
    if (k == j) then
        ! If the current substring has the same number of 0's and 1's, increment the count
        count = count + 1
    end if

    ! Move to the next character
    i = i + 1
end do

! Print the output
write(*,*) count

end
🌐 Data from online sources 
def count_binary_substrings(s: str) -> int:
    prev, curr, result = 0, 1, 0
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            curr += 1
        else:
            result += min(prev, curr)
            prev, curr = curr, 1
    return result + min(prev, curr)

Iterate through the binary string s. Keep track of the count of consecutive equal characters (curr) and the count of consecutive equal characters in the previous group (prev). When we encounter a character different from the previous one, add the minimum of prev and curr to the result. Update prev to the value of curr and reset curr to 1. After the iteration, add the minimum of prev and curr to the result and return the result. This will count all valid binary substrings with consecutive groups of 0's and 1's.

🌐 Data from online sources 
int countBinarySubstrings(string s) {
    int prev = 0, curr = 1, result = 0;
    for (int i = 1; i < s.length(); i++) {
        if (s[i] == s[i - 1]) {
            curr++;
        } else {
            result += min(prev, curr);
            prev = curr;
            curr = 1;
        }
    }
    return result + min(prev, curr);
}

Iterate through the binary string s. Keep track of the count of consecutive equal characters (curr) and the count of consecutive equal characters in the previous group (prev). When we encounter a character different from the previous one, add the minimum of prev and curr to the result. Update prev to the value of curr and reset curr to 1. After the iteration, add the minimum of prev and curr to the result and return the result. This will count all valid binary substrings with consecutive groups of 0's and 1's.