Dada la string binaria str que contiene solo 0 y 1 , la tarea es encontrar el número de substrings que contienen solo 1 y 0 respectivamente, es decir, todos los caracteres son iguales.
Ejemplos:
Entrada: str = «011»
Salida: 4
Explicación:
Tres substrings son «1 « , «1», «11» que tienen solo 1 en ellas, y hay una substring que contiene solo «0».Entrada: str = “0000”
Salida: 10
Explicación:
No hay substrings que contengan todos unos.
Enfoque ingenuo: la idea es generar todas las substrings posibles de la string dada . Para cada substring, verifique si la string contiene solo 1 o solo 0. En caso afirmativo, cuente esa substring. Imprime el recuento de substrings después de las operaciones anteriores.
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)
Enfoque eficiente: la idea es utilizar el concepto de ventana deslizante y el enfoque de dos punteros . A continuación se muestran los pasos para encontrar el recuento de la substring que contiene solo 1 :
- Inicialice dos punteros, diga L y R , e inicialícelos a 0 .
- Ahora itere en la string dada y verifique si el carácter actual es igual a 1 o no. Si es así, extienda la ventana incrementando el valor de R .
- Si el carácter actual es 0 , entonces la ventana L a R – 1 contiene todos unos.
- Agregue el número de substrings de L a R – 1 a la respuesta que es ((R – L) * (R – L + 1)) / 2 e incremente R y reinicie L como R .
- Repita el proceso hasta que L y R se crucen.
- Imprima el recuento de todas las substrings en el paso 4 .
- Para contar el número de substrings con todos 0 , invierta la string dada, es decir, todos los 0 se convertirán en 1 y viceversa.
- Repita los pasos anteriores del paso 1 al paso 4 para el carácter 1 en la string invertida para obtener un recuento de la substring que contiene solo 0 e imprimir el recuento.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to count number of
// sub-strings of a given binary
// string that contains only 1
int countSubAllOnes(string s)
{
int l = 0, r = 0, ans = 0;
// Iterate until L and R cross
// each other
while (l <= r) {
// Check if reached the end
// of string
if (r == s.length()) {
ans += ((r - l) * (r - l + 1)) / 2;
break;
}
// Check if encountered '1'
// then extend window
if (s[r] == '1')
r++;
// Check if encountered '0' then
// add number of strings of
// current window and change the
// values for both l and r
else {
ans += ((r - l) * (r - l + 1)) / 2;
l = r + 1;
r++;
}
}
// Return the answer
return ans;
}
// Function to flip the bits of string
void flip(string& s)
{
for (int i = 0; s[i]; i++) {
if (s[i] == '1')
s[i] = '0';
else
s[i] = '1';
}
cout<<s<<endl;
}
// Function to count number of
// sub-strings of a given binary
// string that contains only 0s & 1s
int countSubAllZerosOnes(string s)
{
// count of substring
// which contains only 1s
int only_1s = countSubAllOnes(s);
// Flip the character of string s
// 0 to 1 and 1 to 0 to count the
// substring with consecutive 0s
flip(s);
cout<<s<<endl;
// count of substring
// which contains only 0s
int only_0s = countSubAllOnes(s);
return only_0s + only_1s;
}
// Driver Code
int main()
{
// Given string str
string s = "011";
// Function Call
cout << countSubAllZerosOnes(s) << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to count number of
// sub-Strings of a given binary
// String that contains only 1
static int countSubAllOnes(String s)
{
int l = 0, r = 0, ans = 0;
// Iterate until L and R cross
// each other
while (l <= r)
{
// Check if reached the end
// of String
if (r == s.length())
{
ans += ((r - l) * (r - l + 1)) / 2;
break;
}
// Check if encountered '1'
// then extend window
if (s.charAt(r) == '1')
r++;
// Check if encountered '0' then
// add number of Strings of
// current window and change the
// values for both l and r
else
{
ans += ((r - l) * (r - l + 1)) / 2;
l = r + 1;
r++;
}
}
// Return the answer
return ans;
}
// Function to flip the bits of String
static String flip(char []s)
{
for(int i = 0; i < s.length; i++)
{
if (s[i] == '1')
s[i] = '0';
else
s[i] = '1';
}
return String.valueOf(s);
}
// Function to count number of
// sub-Strings of a given binary
// String that contains only 0s & 1s
static int countSubAllZerosOnes(String s)
{
// count of subString
// which contains only 1s
int only_1s = countSubAllOnes(s);
// Flip the character of String s
// 0 to 1 and 1 to 0 to count the
// subString with consecutive 0s
s = flip(s.toCharArray());
// count of subString
// which contains only 0s
int only_0s = countSubAllOnes(s);
return only_0s + only_1s;
}
// Driver Code
public static void main(String[] args)
{
// Given String str
String s = "011";
// Function call
System.out.print(countSubAllZerosOnes(s) + "\n");
}
}
// This code is contributed by Rohit_ranjan
Python3
# Python3 program for # the above approach # Function to count number of # sub-strings of a given binary # string that contains only 1 def countSubAllOnes(s): l, r, ans = 0, 0, 0 # Iterate until L and R cross # each other while (l <= r): # Check if reached the end # of string if (r == len(s)): ans += ((r - l) * (r - l + 1)) // 2 break # Check if encountered '1' # then extend window if (s[r] == '1'): r += 1 # Check if encountered '0' then # add number of strings of # current window and change the # values for both l and r else : ans += ((r - l) * (r - l + 1)) // 2 l = r + 1 r += 1 # Return the answer return ans # Function to flip the bits of string def flip(s): arr = list(s) for i in range (len(s)): if (arr[i] == '1'): arr[i] = '0' else: arr[i] = '1' s = ''.join(arr) return s # Function to count number of # sub-strings of a given binary # string that contains only 0s & 1s def countSubAllZerosOnes(s): # count of substring # which contains only 1s only_1s = countSubAllOnes(s) # Flip the character of string s # 0 to 1 and 1 to 0 to count the # substring with consecutive 0s s = flip(s) # count of substring # which contains only 0s only_0s = countSubAllOnes(s) return only_0s + only_1s # Driver Code if __name__ == "__main__": # Given string str s = "011" # Function Call print (countSubAllZerosOnes(s)) # This code is contributed by Chitranayal
C#
// C# program for the above approach
using System;
class GFG{
// Function to count number of
// sub-Strings of a given binary
// String that contains only 1
static int countSubAllOnes(String s)
{
int l = 0, r = 0, ans = 0;
// Iterate until L and R cross
// each other
while (l <= r)
{
// Check if reached the end
// of String
if (r == s.Length)
{
ans += ((r - l) * (r - l + 1)) / 2;
break;
}
// Check if encountered '1'
// then extend window
if (s[r] == '1')
r++;
// Check if encountered '0' then
// add number of Strings of
// current window and change the
// values for both l and r
else
{
ans += ((r - l) * (r - l + 1)) / 2;
l = r + 1;
r++;
}
}
// Return the answer
return ans;
}
// Function to flip the bits of String
static String flip(char []s)
{
for(int i = 0; i < s.Length; i++)
{
if (s[i] == '1')
s[i] = '0';
else
s[i] = '1';
}
return String.Join("",s);
}
// Function to count number of
// sub-Strings of a given binary
// String that contains only 0s & 1s
static int countSubAllZerosOnes(String s)
{
// count of subString
// which contains only 1s
int only_1s = countSubAllOnes(s);
// Flip the character of String s
// 0 to 1 and 1 to 0 to count the
// subString with consecutive 0s
s = flip(s.ToCharArray());
// count of subString
// which contains only 0s
int only_0s = countSubAllOnes(s);
return only_0s + only_1s;
}
// Driver Code
public static void Main(String[] args)
{
// Given String str
String s = "011";
// Function call
Console.Write(countSubAllZerosOnes(s) + "\n");
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// Javascript program for the above approach
// Function to count number of
// sub-strings of a given binary
// string that contains only 1
function countSubAllOnes(s)
{
var l = 0, r = 0, ans = 0;
// Iterate until L and R cross
// each other
while (l <= r) {
// Check if reached the end
// of string
if (r == s.length) {
ans += ((r - l) * (r - l + 1)) / 2;
break;
}
// Check if encountered '1'
// then extend window
if (s[r] == '1')
r++;
// Check if encountered '0' then
// add number of strings of
// current window and change the
// values for both l and r
else {
ans += ((r - l) * (r - l + 1)) / 2;
l = r + 1;
r++;
}
}
// Return the answer
return ans;
}
// Function to flip the bits of string
function flip(s)
{
for (var i = 0; s[i]; i++) {
if (s[i] == '1')
s[i] = '0';
else
s[i] = '1';
}
return s;
}
// Function to count number of
// sub-strings of a given binary
// string that contains only 0s & 1s
function countSubAllZerosOnes(s)
{
// count of substring
// which contains only 1s
var only_1s = countSubAllOnes(s);
// Flip the character of string s
// 0 to 1 and 1 to 0 to count the
// substring with consecutive 0s
s = flip(s.split(''));
// count of substring
// which contains only 0s
var only_0s = countSubAllOnes(s);
return only_0s + only_1s;
}
// Driver Code
// Given string str
var s = "011";
// Function Call
document.write( countSubAllZerosOnes(s));
// This code is contributed by famously.
</script>
Producción:
4
Complejidad de tiempo: O(N), donde N es la longitud de la string dada.
Espacio Auxiliar: O(1)