Dada la string binaria str , la tarea es contar el número total de formas de dividir la string dada en tres substrings que no se superponen y que tienen el mismo número de 0 s.
Ejemplos:
Entrada: str = “01010”
Salida: 4
Explicación:
Las divisiones posibles son: [0, 10, 10], [01, 01, 0], [01, 0, 10], [0, 101, 0]Entrada: str = “11111”
Salida: 0
Planteamiento: Para resolver el problema, la idea es utilizar el concepto de Hashing . A continuación se muestran los pasos para resolver el problema:
- Itere sobre la string y cuente el número total de ceros y guárdelo en una variable, digamos total_count .
- Use un Hashmap , digamos map , para almacenar la frecuencia de la suma acumulada de 0s.
- Inicialice una variable k con total_count/3 que denota el número de 0 requerido en cada partición.
- Inicialice las variables res y sum para almacenar el número de formas de dividir la string y la suma acumulativa de 0 s respectivamente.
- Iterar sobre la string dada e incrementar la suma , si el carácter actual es 0 .
- Incremente res por map[k] , si sum = 2k y k existen en el mapa.
- Actualice la frecuencia de la suma en el mapa.
- Devuelve res al final.
- Retorna 0, si total_count no es divisible por 3 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to return ways to split
// a string into three parts
// with the equal number of 0
int count(string s)
{
// Store total count of 0s
int cnt = 0;
// Count total no. of 0s
// character in given string
for(char c : s)
{
cnt += c == '0' ? 1 : 0;
}
// If total count of 0
// character is not
// divisible by 3
if (cnt % 3 != 0)
return 0;
int res = 0, k = cnt / 3, sum = 0;
// Initialize mp to store
// frequency of k
map<int, int> mp;
// Traverse string to find
// ways to split string
for(int i = 0; i < s.length(); i++)
{
// Increment count if 0 appears
sum += s[i] == '0' ? 1 : 0;
// Increment result if sum equal to
// 2*k and k exists in mp
if (sum == 2 * k && mp.find(k) != mp.end() &&
i < s.length() - 1 && i > 0)
{
res += mp[k];
}
// Insert sum in mp
mp[sum]++;
}
// Return result
return res;
}
// Driver Code
int main()
{
// Given string
string str = "01010";
// Function call
cout << count(str);
}
// This code is contributed by rutvik_56
Java
// Java implementation for the above approach
import java.util.*;
import java.lang.*;
class GFG {
// Function to return ways to split
// a string into three parts
// with the equal number of 0
static int count(String s)
{
// Store total count of 0s
int cnt = 0;
// Count total no. of 0s
// character in given string
for (char c : s.toCharArray()) {
cnt += c == '0' ? 1 : 0;
}
// If total count of 0
// character is not
// divisible by 3
if (cnt % 3 != 0)
return 0;
int res = 0, k = cnt / 3, sum = 0;
// Initialize map to store
// frequency of k
Map<Integer, Integer> map = new HashMap<>();
// Traverse string to find
// ways to split string
for (int i = 0; i < s.length(); i++) {
// Increment count if 0 appears
sum += s.charAt(i) == '0' ? 1 : 0;
// Increment result if sum equal to
// 2*k and k exists in map
if (sum == 2 * k && map.containsKey(k)
&& i < s.length() - 1 && i > 0) {
res += map.get(k);
}
// Insert sum in map
map.put(sum,
map.getOrDefault(sum, 0) + 1);
}
// Return result
return res;
}
// Driver Code
public static void main(String[] args)
{
// Given string
String str = "01010";
// Function call
System.out.println(count(str));
}
}
Python3
# Python3 implementation for
# the above approach
# Function to return ways to split
# a string into three parts
# with the equal number of 0
def count(s):
# Store total count of 0s
cnt = 0
# Count total no. of 0s
# character in given string
for c in s:
if c == '0':
cnt += 1
# If total count of 0
# character is not
# divisible by 3
if (cnt % 3 != 0):
return 0
res = 0
k = cnt // 3
sum = 0
# Initialize map to store
# frequency of k
mp = {}
# Traverse string to find
# ways to split string
for i in range(len(s)):
# Increment count if 0 appears
if s[i] == '0':
sum += 1
# Increment result if sum equal to
# 2*k and k exists in map
if (sum == 2 * k and k in mp and
i < len(s) - 1 and i > 0):
res += mp[k]
# Insert sum in map
if sum in mp:
mp[sum] += 1
else:
mp[sum] = 1
# Return result
return res
# Driver Code
if __name__ == "__main__":
# Given string
st = "01010"
# Function call
print(count(st))
# This code is contributed by Chitranayal
C#
// C# implementation for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to return ways to split
// a string into three parts
// with the equal number of 0
static int count(String s)
{
// Store total count of 0s
int cnt = 0;
// Count total no. of 0s
// character in given string
foreach(char c in s.ToCharArray())
{
cnt += c == '0' ? 1 : 0;
}
// If total count of 0
// character is not
// divisible by 3
if (cnt % 3 != 0)
return 0;
int res = 0, k = cnt / 3, sum = 0;
// Initialize map to store
// frequency of k
Dictionary<int,
int> map = new Dictionary<int,
int>();
// Traverse string to find
// ways to split string
for(int i = 0; i < s.Length; i++)
{
// Increment count if 0 appears
sum += s[i] == '0' ? 1 : 0;
// Increment result if sum equal to
// 2*k and k exists in map
if (sum == 2 * k && map.ContainsKey(k) &&
i < s.Length - 1 && i > 0)
{
res += map[k];
}
// Insert sum in map
if(map.ContainsKey(sum))
map[sum] = map[sum] + 1;
else
map.Add(sum, 1);
}
// Return result
return res;
}
// Driver Code
public static void Main(String[] args)
{
// Given string
String str = "01010";
// Function call
Console.WriteLine(count(str));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript implementation for the above approach
// Function to return ways to split
// a string into three parts
// with the equal number of 0
function count(s)
{
// Store total count of 0s
var cnt = 0;
// Count total no. of 0s
// character in given string
s.split('').forEach(c => {
cnt += (c == '0') ? 1 : 0;
});
// If total count of 0
// character is not
// divisible by 3
if (cnt % 3 != 0)
return 0;
var res = 0, k = parseInt(cnt / 3), sum = 0;
// Initialize mp to store
// frequency of k
var mp = new Map();
// Traverse string to find
// ways to split string
for(var i = 0; i < s.length; i++)
{
// Increment count if 0 appears
sum += (s[i] == '0') ? 1 : 0;
// Increment result if sum equal to
// 2*k and k exists in mp
if (sum == 2 * k && mp.has(k) &&
i < s.length - 1 && i > 0)
{
res += mp.get(k);
}
// Insert sum in mp
if(mp.has(sum))
mp.set(sum, mp.get(sum)+1)
else
mp.set(sum, 1);
}
// Return result
return res;
}
// Driver Code
// Given string
var str = "01010";
// Function call
document.write( count(str));
</script>
Producción
4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
ENFOQUE EFICIENTE:
Para dividir la string de entrada en tres partes, solo se necesitan dos cortes, lo que dará tres substrings: S1, S2 y S3. Cada substring tendrá el mismo número de 0 y será (número total de 0)/3. Ahora mantenga un registro del conteo del número de 0 desde el comienzo de la string. Una vez que el conteo sea igual a (número total de 0)/3, haga el primer corte. De manera similar, haga el segundo corte una vez que el conteo de 0 sea igual a 2*(número total de 1)/3.
Algoritmo
- Cuente el número de 0. Si no es divisible por 3, entonces respuesta = 0.
- Si el recuento es 0, cada substring tendrá el mismo número de ‘0’, es decir, cero número de ‘0’. Por lo tanto, el número total de formas de dividir la string dada es el número de combinaciones de seleccionar 2 lugares para dividir la string de n-1 lugares. Para la primera selección, tenemos n-1 opciones y para la segunda selección, tenemos n-2 opciones. Por lo tanto, el número total de combinaciones es (n-1)*(n-2). Dado que las selecciones son idénticas, divídalo por un factorial de 2. Así que responda = ((n-1)*(n-2))/2.
- Recorre la string dada desde el principio y lleva la cuenta del número de ‘0’ nuevamente, si la cuenta llega al (número total de ‘0’)/3, comenzamos a acumular el número de vías del 1er corte; cuando el conteo llega a 2*(número total de ‘0s’)/3, comenzamos a acumular el número de vías del 2do corte.
- La respuesta es la multiplicación del número de formas del primer corte y del segundo corte.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// the number of ways to split
int splitstring(string s)
{
int n = s.length();
// Calculating the total
// number of zeros
int zeros = 0;
for (int i = 0; i < n; i++)
if (s[i] == '0')
zeros++;
// Case1
// If total count of zeros is not
// divisible by 3
if (zeros % 3 != 0)
return 0;
// Case2
// if total count of zeros
// is zero
if (zeros == 0)
return ((n - 1) * (n - 2)) / 2;
// Case3
// General case
// Number of zeros in each substring
int zerosInEachSubstring = zeros / 3;
// Initialising zero to the number of ways
// for first and second cut
int waysOfFirstCut = 0, waysOfSecondCut = 0;
// Initializing the count
int count = 0;
// Traversing from the beginning
for (int i = 0; i < n; i++)
{
// Incrementing the count
// if the element is '0'
if (s[i] == '0')
count++;
// Incrementing the ways for the
// 1st cut if count is equal to
// zeros required in each substring
if (count == zerosInEachSubstring)
waysOfFirstCut++;
// Incrementing the ways for the
// 2nd cut if count is equal to
// 2*(zeros required in each substring)
else if (count == 2 * zerosInEachSubstring)
waysOfSecondCut++;
}
// Total number of ways to split is
// multiplication of ways for the 1st
// and 2nd cut
return waysOfFirstCut * waysOfSecondCut;
}
// Driver Code
int main()
{
string s = "01010";
// Function Call
cout << "The number of ways to split is "
<< splitstring(s) << endl;
}
// this code is contributed by Arif
Java
// Java program for above approach
import java.util.*;
class GFG{
// Function to calculate
// the number of ways to split
static int splitstring(String s)
{
int n = s.length();
// Calculating the total
// number of zeros
int zeros = 0;
for(int i = 0; i < n; i++)
if (s.charAt(i) == '0')
zeros++;
// Case1
// If total count of zeros is not
// divisible by 3
if (zeros % 3 != 0)
return 0;
// Case2
// if total count of zeros
// is zero
if (zeros == 0)
return ((n - 1) * (n - 2)) / 2;
// Case3
// General case
// Number of zeros in each substring
int zerosInEachSubstring = zeros / 3;
// Initialising zero to the number of ways
// for first and second cut
int waysOfFirstCut = 0;
int waysOfSecondCut = 0;
// Initializing the count
int count = 0;
// Traversing from the beginning
for(int i = 0; i < n; i++)
{
// Incrementing the count
// if the element is '0'
if (s.charAt(i) == '0')
count++;
// Incrementing the ways for the
// 1st cut if count is equal to
// zeros required in each substring
if (count == zerosInEachSubstring)
waysOfFirstCut++;
// Incrementing the ways for the
// 2nd cut if count is equal to
// 2*(zeros required in each substring)
else if (count == 2 * zerosInEachSubstring)
waysOfSecondCut++;
}
// Total number of ways to split is
// multiplication of ways for the 1st
// and 2nd cut
return waysOfFirstCut * waysOfSecondCut;
}
// Driver Code
public static void main(String args[])
{
String s = "01010";
// Function Call
System.out.println("The number of " +
"ways to split is " +
splitstring(s));
}
}
// This code is contributed by Stream_Cipher
Python3
# Python3 program for above approach
# Function to calculate
# the number of ways to split
def splitstring(s):
n = len(s)
# Calculating the total
# number of zeros
zeros = 0
for i in range(n):
if s[i] == '0':
zeros += 1
# Case1
# If total count of zeros is not
# divisible by 3
if zeros % 3 != 0:
return 0
# Case2
# if total count of zeros
# is zero
if zeros == 0:
return ((n - 1) *
(n - 2)) // 2
# Case3
# General case
# Number of zeros in each substring
zerosInEachSubstring = zeros // 3
# Initialising zero to the number of ways
# for first and second cut
waysOfFirstCut, waysOfSecondCut = 0, 0
# Initializing the count
count = 0
# Traversing from the beginning
for i in range(n):
# Incrementing the count
# if the element is '0'
if s[i] == '0':
count += 1
# Incrementing the ways for the
# 1st cut if count is equal to
# zeros required in each substring
if (count == zerosInEachSubstring):
waysOfFirstCut += 1
# Incrementing the ways for the
# 2nd cut if count is equal to
# 2*(zeros required in each substring)
elif (count == 2 * zerosInEachSubstring):
waysOfSecondCut += 1
# Total number of ways to split is
# multiplication of ways for the 1st
# and 2nd cut
return waysOfFirstCut * waysOfSecondCut
# Driver code
s = "01010"
# Function call
print("The number of ways to split is", splitstring(s))
# This code is contributed by divyeshrabadiya07
C#
// C# program for above approach
using System.Collections.Generic;
using System;
class GFG{
// Function to calculate
// the number of ways to split
static int splitstring(string s)
{
int n = s.Length;
// Calculating the total
// number of zeros
int zeros = 0;
for(int i = 0; i < n; i++)
if (s[i] == '0')
zeros++;
// Case1
// If total count of zeros is not
// divisible by 3
if (zeros % 3 != 0)
return 0;
// Case2
// if total count of zeros
// is zero
if (zeros == 0)
return ((n - 1) * (n - 2)) / 2;
// Case3
// General case
// Number of zeros in each substring
int zerosInEachSubstring = zeros / 3;
// Initialising zero to the number of ways
// for first and second cut
int waysOfFirstCut = 0;
int waysOfSecondCut = 0;
// Initializing the count
int count = 0;
// Traversing from the beginning
for(int i = 0; i < n; i++)
{
// Incrementing the count
// if the element is '0'
if (s[i] == '0')
count++;
// Incrementing the ways for the
// 1st cut if count is equal to
// zeros required in each substring
if (count == zerosInEachSubstring)
waysOfFirstCut++;
// Incrementing the ways for the
// 2nd cut if count is equal to
// 2*(zeros required in each substring)
else if (count == 2 * zerosInEachSubstring)
waysOfSecondCut++;
}
// Total number of ways to split is
// multiplication of ways for the 1st
// and 2nd cut
return waysOfFirstCut * waysOfSecondCut;
}
// Driver Code
public static void Main()
{
string s = "01010";
// Function call
Console.WriteLine("The number of ways " +
"to split is " +
splitstring(s));
}
}
// This code is contributed by Stream_Cipher
Javascript
<script>
// Javascript program for above approach
// Function to calculate
// the number of ways to split
function splitstring(s)
{
let n = s.length;
// Calculating the total
// number of zeros
let zeros = 0;
for(let i = 0; i < n; i++)
if (s[i] == '0')
zeros++;
// Case1
// If total count of zeros is not
// divisible by 3
if (zeros % 3 != 0)
return 0;
// Case2
// if total count of zeros
// is zero
if (zeros == 0)
return parseInt(((n - 1) * (n - 2)) / 2, 10);
// Case3
// General case
// Number of zeros in each substring
let zerosInEachSubstring = parseInt(zeros / 3, 10);
// Initialising zero to the number of ways
// for first and second cut
let waysOfFirstCut = 0;
let waysOfSecondCut = 0;
// Initializing the count
let count = 0;
// Traversing from the beginning
for(let i = 0; i < n; i++)
{
// Incrementing the count
// if the element is '0'
if (s[i] == '0')
count++;
// Incrementing the ways for the
// 1st cut if count is equal to
// zeros required in each substring
if (count == zerosInEachSubstring)
waysOfFirstCut++;
// Incrementing the ways for the
// 2nd cut if count is equal to
// 2*(zeros required in each substring)
else if (count == 2 * zerosInEachSubstring)
waysOfSecondCut++;
}
// Total number of ways to split is
// multiplication of ways for the 1st
// and 2nd cut
return waysOfFirstCut * waysOfSecondCut;
}
let s = "01010";
// Function call
document.write("The number of ways " +
"to split is " +
splitstring(s));
</script>
Producción
The number of ways to split is 4
Complejidad de tiempo : O(n)
Complejidad espacial : O(1)