Dada la string binaria str de 0 y 1 solamente. La tarea es contar el número total de substrings de la string str de modo que cada substring tenga el mismo número de 0 y 1 consecutivos .
Ejemplos
Entrada: str = “010011”
Salida: 4
Explicación:
Las substrings con 0 y 1 consecutivos son “01”, “10”, “0011”, “01”. Por lo tanto, la cuenta es 4.
Nota:
Los dos «01» están en posiciones diferentes: [0, 1] y [3, 4].
“010011” tiene el mismo número de 0 y 1 pero no son consecutivos.
Entrada: str = “0001110010”
Salida: 7
Explicación:
Las substrings con 0 y 1 consecutivos son “000111”, “0011”, “01”, “1100”, “10”, “01”, “10”.
Acercarse:
- Cuente el número de 0 (o 1) consecutivos desde el inicio de la string.
- Luego cuente el número de 1 (o 0) consecutivos desde la posición en la string str donde termina el conteo de 0 (o 1).
- El número total de substrings con 0 y 1 consecutivos es el mínimo del conteo de 0 y 1 consecutivos encontrado en los dos pasos anteriores.
- Repita los pasos anteriores hasta el final de la string str .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the count of substrings with equal no.
// of consecutive 0's and 1's
int countSubstring(string& S, int& n)
{
// To store the total count of substrings
int ans = 0;
int i = 0;
// Traversing the string
while (i < n) {
// Count of consecutive 0's & 1's
int cnt0 = 0, cnt1 = 0;
// Counting subarrays of type "01"
if (S[i] == '0') {
// Count the consecutive 0's
while (i < n && S[i] == '0') {
cnt0++;
i++;
}
// If consecutive 0's ends then check for
// consecutive 1's
int j = i;
// Counting consecutive 1's
while (j < n && S[j] == '1') {
cnt1++;
j++;
}
}
// Counting subarrays of type "10"
else {
// Count consecutive 1's
while (i < n && S[i] == '1') {
cnt1++;
i++;
}
// If consecutive 1's ends then check for
// consecutive 0's
int j = i;
// Count consecutive 0's
while (j < n && S[j] == '0') {
cnt0++;
j++;
}
}
// Update the total count of substrings with minimum
// of (cnt0, cnt1)
ans += min(cnt0, cnt1);
}
// Return answer
return ans;
}
// Driver code
int main()
{
string S = "0001110010";
int n = S.length();
// Function to print the count of substrings
cout << countSubstring(S, n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C implementation of the above approach
#include <stdio.h>
#include <string.h>
// Find minimum between two numbers.
int min(int num1, int num2)
{
return (num1 > num2) ? num2 : num1;
}
// Function to find the count of substrings with equal no.
// of consecutive 0's and 1's
int countSubstring(char S[], int n)
{
// To store the total count of substrings
int ans = 0;
int i = 0;
// Traversing the string
while (i < n) {
// Count of consecutive 0's & 1's
int cnt0 = 0, cnt1 = 0;
// Counting subarrays of type "01"
if (S[i] == '0') {
// Count the consecutive 0's
while (i < n && S[i] == '0') {
cnt0++;
i++;
}
// If consecutive 0's ends then check for
// consecutive 1's
int j = i;
// Counting consecutive 1's
while (j < n && S[j] == '1') {
cnt1++;
j++;
}
}
// Counting subarrays of type "10"
else {
// Count consecutive 1's
while (i < n && S[i] == '1') {
cnt1++;
i++;
}
// If consecutive 1's ends then check for
// consecutive 0's
int j = i;
// Count consecutive 0's
while (j < n && S[j] == '0') {
cnt0++;
j++;
}
}
// Update the total count of substrings with minimum
// of (cnt0, cnt1)
ans += min(cnt0, cnt1);
}
// Return answer
return ans;
}
// Driver code
int main()
{
char S[] = "0001110010";
int n = strlen(S);
// Function to print the count of substrings
printf("%d", countSubstring(S, n));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java implementation of the above approach
class GFG {
// Function to find the count of substrings with equal
// no. of consecutive 0's and 1's
static int countSubstring(String S, int n)
{
// To store the total count of substrings
int ans = 0;
int i = 0;
// Traversing the string
while (i < n) {
// Count of consecutive 0's & 1's
int cnt0 = 0, cnt1 = 0;
// Counting subarrays of type "01"
if (S.charAt(i) == '0') {
// Count the consecutive 0's
while (i < n && S.charAt(i) == '0') {
cnt0++;
i++;
}
// If consecutive 0's ends then check for
// consecutive 1's
int j = i;
// Counting consecutive 1's
while (j < n && S.charAt(j) == '1') {
cnt1++;
j++;
}
}
// Counting subarrays of type "10"
else {
// Count consecutive 1's
while (i < n && S.charAt(i) == '1') {
cnt1++;
i++;
}
// If consecutive 1's ends then check for
// consecutive 0's
int j = i;
// Count consecutive 0's
while (j < n && S.charAt(j) == '0') {
cnt0++;
j++;
}
}
// Update the total count of substrings with
// minimum of (cnt0, cnt1)
ans += Math.min(cnt0, cnt1);
}
// Return answer
return ans;
}
// Driver code
static public void main(String args[])
{
String S = "0001110010";
int n = S.length();
// Function to print the count of substrings
System.out.println(countSubstring(S, n));
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 implementation of the # above approach # Function to find the count # of substrings with equal no. # of consecutive 0's and 1's def countSubstring(S, n) : # To store the total count # of substrings ans = 0; i = 0; # Traversing the string while (i < n) : # Count of consecutive # 0's & 1's cnt0 = 0; cnt1 = 0; # Counting subarrays of # type "01" if (S[i] == '0') : # Count the consecutive # 0's while (i < n and S[i] == '0') : cnt0 += 1; i += 1; # If consecutive 0's # ends then check for # consecutive 1's j = i; # Counting consecutive 1's while (j < n and S[j] == '1') : cnt1 += 1; j += 1; # Counting subarrays of # type "10" else : # Count consecutive 1's while (i < n and S[i] == '1') : cnt1 += 1; i += 1; # If consecutive 1's # ends then check for # consecutive 0's j = i; # Count consecutive 0's while (j < n and S[j] == '0') : cnt0 += 1; j += 1; # Update the total count # of substrings with # minimum of (cnt0, cnt1) ans += min(cnt0, cnt1); # Return answer return ans; # Driver code if __name__ == "__main__" : S = "0001110010"; n = len(S); # Function to print the # count of substrings print(countSubstring(S, n)); # This code is contributed by Yash_R
C#
// C# implementation of the
// above approach
using System;
class GFG{
// Function to find the count
// of substrings with equal no.
// of consecutive 0's and 1's
static int countSubstring(string S, int n)
{
// To store the total count
// of substrings
int ans = 0;
int i = 0;
// Traversing the string
while (i < n) {
// Count of consecutive
// 0's & 1's
int cnt0 = 0, cnt1 = 0;
// Counting subarrays of
// type "01"
if (S[i] == '0') {
// Count the consecutive
// 0's
while (i < n && S[i] == '0') {
cnt0++;
i++;
}
// If consecutive 0's
// ends then check for
// consecutive 1's
int j = i;
// Counting consecutive 1's
while (j < n && S[j] == '1') {
cnt1++;
j++;
}
}
// Counting subarrays of
// type "10"
else {
// Count consecutive 1's
while (i < n && S[i] == '1') {
cnt1++;
i++;
}
// If consecutive 1's
// ends then check for
// consecutive 0's
int j = i;
// Count consecutive 0's
while (j < n && S[j] == '0') {
cnt0++;
j++;
}
}
// Update the total count
// of substrings with
// minimum of (cnt0, cnt1)
ans += Math.Min(cnt0, cnt1);
}
// Return answer
return ans;
}
// Driver code
static public void Main ()
{
string S = "0001110010";
int n = S.Length;
// Function to print the
// count of substrings
Console.WriteLine(countSubstring(S, n));
}
}
// This code is contributed by Yash_R
Javascript
<script>
// Javascript implementation of the
// above approach
// Function to find the count
// of substrings with equal no.
// of consecutive 0's and 1's
function countSubstring( S , n)
{
// To store the total count
// of substrings
var ans = 0;
var i = 0;
// Traversing the string
while (i < n) {
// Count of consecutive
// 0's & 1's
var cnt0 = 0, cnt1 = 0;
// Counting subarrays of
// type "01"
if (S.charAt(i) == '0') {
// Count the consecutive
// 0's
while (i < n && S.charAt(i) == '0')
{
cnt0++;
i++;
}
// If consecutive 0's
// ends then check for
// consecutive 1's
var j = i;
// Counting consecutive 1's
while (j < n && S.charAt(j) == '1')
{
cnt1++;
j++;
}
}
// Counting subarrays of
// type "10"
else {
// Count consecutive 1's
while (i < n && S.charAt(i) == '1')
{
cnt1++;
i++;
}
// If consecutive 1's
// ends then check for
// consecutive 0's
var j = i;
// Count consecutive 0's
while (j < n && S.charAt(j) == '0')
{
cnt0++;
j++;
}
}
// Update the total count
// of substrings with
// minimum of (cnt0, cnt1)
ans += Math.min(cnt0, cnt1);
}
// Return answer
return ans;
}
// Driver code
var S = "0001110010";
var n = S.length;
// Function to print the
// count of substrings
document.write(countSubstring(S, n));
// This code contributed by umadevi9616
</script>
Producción:
7
Complejidad de tiempo: O(N), donde N = longitud de la string.
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA