将二进制字符串拆分为0和1相等数量的子字符串

本文概述

• C ++
• Java
• Python3
• C#

给定一个二进制字符串str长度ñ, 任务是查找子字符串的最大数量str可以划分为使得所有子串都平衡的状态, 即它们具有相同数量的0s和1s。如果不可能分裂str满足条件然后打印-1.

例子：

输入：str =" 0100110101"
输出：4
所需的子字符串为" 01", " 0011", " 01"和" 01"。
输入：str =" 0111100010"
输出：3

方法：初始化计数= 0并逐个字符地遍历字符串, 并跟踪0s和1s到目前为止, 每当0s和1s变得相等, 增加计数。如果算0s和1s原字符串中的不等于则打印-1否则, 在遍历整个字符串之后打印count的值。

下面是上述方法的实现：

C ++

//C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
//Function to return the count
//of maximum substrings str
//can be divided into
int maxSubStr(string str, int n)
{
  
     //To store the count of 0s and 1s
     int count0 = 0, count1 = 0;
  
     //To store the count of maximum
     //substrings str can be divided into
     int cnt = 0;
     for ( int i = 0; i <n; i++) {
         if (str[i] == '0' ) {
             count0++;
         }
         else {
             count1++;
         }
         if (count0 == count1) {
             cnt++;
         }
     }
  
     //It is not possible to
     //split the string
     if (count0 != count1) {
         return -1;
     }
  
     return cnt;
}
  
//Driver code
int main()
{
     string str = "0100110101" ;
     int n = str.length();
  
     cout <<maxSubStr(str, n);
  
     return 0;
}

Java

//Java implementation of the above approach
class GFG
{
  
//Function to return the count
//of maximum substrings str
//can be divided into
static int maxSubStr(String str, int n)
{
  
     //To store the count of 0s and 1s
     int count0 = 0 , count1 = 0 ;
  
     //To store the count of maximum
     //substrings str can be divided into
     int cnt = 0 ;
     for ( int i = 0 ; i <n; i++)
     {
         if (str.charAt(i) == '0' ) 
         {
             count0++;
         }
         else 
         {
             count1++;
         }
         if (count0 == count1) 
         {
             cnt++;
         }
     }
  
     //It is not possible to
     //split the string
     if (count0 != count1) 
     {
         return - 1 ;
     }
     return cnt;
}
  
//Driver code
public static void main(String []args) 
{
     String str = "0100110101" ;
     int n = str.length();
  
     System.out.println(maxSubStr(str, n));
}
}
  
//This code is contributed by PrinciRaj1992

Python3

# Python3 implementation of the approach
  
# Function to return the count 
# of maximum substrings str 
# can be divided into
def maxSubStr( str , n):
      
     # To store the count of 0s and 1s
     count0 = 0
     count1 = 0
      
     # To store the count of maximum 
     # substrings str can be divided into
     cnt = 0
      
     for i in range (n):
         if str [i] = = '0' :
             count0 + = 1
         else :
             count1 + = 1
              
         if count0 = = count1:
             cnt + = 1
  
# It is not possible to 
     # split the string
     if count0 ! = count1:
         return - 1
              
     return cnt
  
# Driver code
str = "0100110101"
n = len ( str )
print (maxSubStr( str , n))

C#

//C# implementation of the above approach
using System;
  
class GFG
{
  
//Function to return the count
//of maximum substrings str
//can be divided into
static int maxSubStr(String str, int n)
{
  
     //To store the count of 0s and 1s
     int count0 = 0, count1 = 0;
  
     //To store the count of maximum
     //substrings str can be divided into
     int cnt = 0;
     for ( int i = 0; i <n; i++)
     {
         if (str[i] == '0' ) 
         {
             count0++;
         }
         else
         {
             count1++;
         }
         if (count0 == count1) 
         {
             cnt++;
         }
     }
  
     //It is not possible to
     //split the string
     if (count0 != count1) 
     {
         return -1;
     }
     return cnt;
}
  
//Driver code
public static void Main(String []args) 
{
     String str = "0100110101" ;
     int n = str.Length;
  
     Console.WriteLine(maxSubStr(str, n));
}
}
  
//This code is contributed by PrinciRaj1992

输出如下：

4

时间复杂度：O(N)其中N是字符串的长度

空间复杂度：O(1)

---