Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/696.html

696. Count Binary Substrings

Level

Easy

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.

Solution

First find the indices where the character is different to its next character.

Next, for each index found, use two pointers to point to the left index and the right index. While characters in the left half of the substring are consecutive 0’s and characters in the right half of the substring are consecutive 1’s, or characters in the left half of the substring are consecutive 1’s and characters in the right half of the substring are consecutive 0’s, move both pointers toward the ends of the string by 1 step, and count the number of binary substrings.

Finally, return the number of binary substrings.

• Java
• C++
• Python
• Go

• class Solution {
      public int countBinarySubstrings(String s) {
          int count = 0;
          int length = s.length();
          List<Integer> indices = new ArrayList<Integer>();
          for (int i = 0; i < length - 1; i++) {
              if (s.charAt(i) != s.charAt(i + 1))
                  indices.add(i);
          }
          for (int index : indices) {
              int indexLeft = index, indexRight = index + 1;
              char charLeft = s.charAt(indexLeft), charRight = s.charAt(indexRight);
              while (indexLeft >= 0 && indexRight < length) {
                  if (s.charAt(indexLeft) != charLeft || s.charAt(indexRight) != charRight)
                      break;
                  count++;
                  indexLeft--;
                  indexRight++;
              }
          }
          return count;
      }
  }
  
  ############
  
  class Solution {
      public int countBinarySubstrings(String s) {
          int i = 0, n = s.length();
          List<Integer> t = new ArrayList<>();
          while (i < n) {
              int cnt = 1;
              while (i + 1 < n && s.charAt(i + 1) == s.charAt(i)) {
                  ++i;
                  ++cnt;
              }
              t.add(cnt);
              ++i;
          }
          int ans = 0;
          for (i = 1; i < t.size(); ++i) {
              ans += Math.min(t.get(i - 1), t.get(i));
          }
          return ans;
      }
  }
  

• // OJ: https://leetcode.com/problems/count-binary-substrings/
  // Time: O(N)
  // Space: O(1)
  class Solution {
  public:
      int countBinarySubstrings(string s) {
          int prev = 0, N = s.size(), ans = 0;
          for (int i = 0; i < N; ) {
              int j = i++;
              while (i < N && s[i] == s[i - 1]) ++i;
              int cnt = i - j;
              ans += min(cnt, prev);
              prev = cnt;
          }
          return ans;
      }
  };
  

• class Solution:
      def countBinarySubstrings(self, s: str) -> int:
          i, n = 0, len(s)
          t = []
          while i < n:
              cnt = 1
              while i + 1 < n and s[i + 1] == s[i]:
                  cnt += 1
                  i += 1
              t.append(cnt)
              i += 1
          ans = 0
          for i in range(1, len(t)):
              ans += min(t[i - 1], t[i])
          return ans
  
  ############
  
  class Solution(object):
      def countBinarySubstrings(self, s):
          """
          :type s: str
          :rtype: int
          """
          N = len(s)
          res = 0
          for i in range(N):
              c1, c0 = 0, 0
              if s[i] == "1":
                  c1 = 1
              else:
                  c0 = 1
              for j in range(i + 1, N):
                  if s[j] == "1":
                      c1 += 1
                  else:
                      c0 += 1
                  if c0 == c1:
                      res += 1
                      break
          return res
  

• func countBinarySubstrings(s string) int {
  	i, n := 0, len(s)
  	var t []int
  	for i < n {
  		cnt := 1
  		for i+1 < n && s[i+1] == s[i] {
  			i++
  			cnt++
  		}
  		t = append(t, cnt)
  		i++
  	}
  	ans := 0
  	for i := 1; i < len(t); i++ {
  		ans += min(t[i-1], t[i])
  	}
  	return ans
  }
  
  func min(a, b int) int {
  	if a < b {
  		return a
  	}
  	return b
  }
  

All Problems

All Solutions