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

本文概述

  • C ++
  • Java
  • Python3
  • C#
给定一个二进制字符串str长度?, 任务是查找子字符串的最大数量str可以划分为使得所有子串都平衡的状态, 即它们具有相同数量的0s和1s。如果不可能分裂str满足条件然后打印-1.
例子:
【将二进制字符串拆分为0和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 = 0for i in range (n): if str [i] = = '0' : count0 + = 1 else : count1 + = 1if count0 = = count1: cnt + = 1# It is not possible to # split the string if count0 ! = count1: return - 1return 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)

    推荐阅读