Dada una string binaria de tamaño N , la tarea es contar el número de substrings alternas que están presentes en la string S.
Ejemplos:
Entrada: S = “0010”
Salida: 7
Explicación:
Todas las substrings de las strings S son: {“0”, “00”, “001”, “0010”, “0”, “01”, “010”, “ 1”, “10”, “0”}
Strings que se alternan: {“0”, “0”, “01”, “010”, “1”, “10”, “0”}.
Por lo tanto, la respuesta es 7.Entrada: S = “010”
Salida: 6
Enfoque ingenuo: el enfoque más simple para resolver este problema es primero, encontrar todas las substrings de la string S , luego verificar cada string si está alternando o no.
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(N 2 )
Enfoque eficiente: este problema tiene la propiedad de subproblemas superpuestos y la propiedad de subestructura óptima . Entonces este problema se puede resolver usando Programación Dinámica . Siga los pasos a continuación para resolver este problema:
- Declare una array dp , donde dp[i][j] almacena la cantidad de strings alternas que comienzan con char i y están en el rango [j, N-1] .
- Iterar en el rango [N-1, 0] usando la variable i y realizar los siguientes pasos:
- Si i es igual a N-1 , entonces si el carácter actual es ‘1’ , entonces asigne 1 a dp[1][i] , de lo contrario asigne 1 a dp[0][i] .
- De lo contrario, si el carácter actual es ‘0’ , actualice dp[0][i] a 1+dp[1][i+1] , de lo contrario, actualice dp[1][i] a 1+dp[0][ i+1].
- Inicialice una variable, por ejemplo , ans como 0 para almacenar el número de substrings que se alternan.
- Iterar en el rango [0, N-1] usando la variable i y realizar los siguientes pasos:
- Actualizar ans como máximo de dp[0][i] y dp[1][i].
- Finalmente, imprima el valor obtenido en ans como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// c++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count number of alternating
// substrings from a given binary string
int countAlternatingSubstrings(string S, int N)
{
// Initialize dp array, where dp[i][j] stores
// the number of alternating strings starts
// with i and having j elements.
vector<vector<int> > dp(2, vector<int>(N, 0));
// Traverse the string from the end
for (int i = N - 1; i >= 0; i--) {
// If i is equal to N - 1
if (i == N - 1) {
if (S[i] == '1')
dp[1][i] = 1;
else
dp[0][i] = 1;
}
// Otherwise,
else {
// Increment count of
// substrings starting at i
// and has 0 in the beginning
if (S[i] == '0')
dp[0][i] = 1 + dp[1][i + 1];
// Increment count of
// substrings starting at i
// and has 1 in the beginning
else
dp[1][i] = 1 + dp[0][i + 1];
}
}
// Stores the result
int ans = 0;
// Iterate in the range [0, N-1]
for (int i = 0; i < N; i++) {
// Update ans
ans += max(dp[0][i], dp[1][i]);
}
// Return the ans
return ans;
}
// Driver code
int main()
{
// Given Input
string S = "0010";
int N = S.length();
// Function call
cout << countAlternatingSubstrings(S, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to count number of alternating
// substrings from a given binary string
static int countAlternatingSubstrings(String S, int N)
{
// Initialize dp array, where dp[i][j] stores
// the number of alternating strings starts
// with i and having j elements.
int[][] dp = new int[2][N];
for(int i = 0; i < 2; i++)
{
for(int j = 0; j < N; j++)
{
dp[i][j] = 0;
}
}
// Traverse the string from the end
for(int i = N - 1; i >= 0; i--)
{
// If i is equal to N - 1
if (i == N - 1)
{
if (S.charAt(i) == '1')
dp[1][i] = 1;
else
dp[0][i] = 1;
}
// Otherwise,
else
{
// Increment count of
// substrings starting at i
// and has 0 in the beginning
if (S.charAt(i) == '0')
dp[0][i] = 1 + dp[1][i + 1];
// Increment count of
// substrings starting at i
// and has 1 in the beginning
else
dp[1][i] = 1 + dp[0][i + 1];
}
}
// Stores the result
int ans = 0;
// Iterate in the range [0, N-1]
for(int i = 0; i < N; i++)
{
// Update ans
ans += Math.max(dp[0][i], dp[1][i]);
}
// Return the ans
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given Input
String S = "0010";
int N = S.length();
// Function call
System.out.print(countAlternatingSubstrings(S, N));
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach # Function to count number of alternating # substrings from a given binary string def countAlternatingSubstrings(S, N): # Initialize dp array, where dp[i][j] stores # the number of alternating strings starts # with i and having j elements. dp = [[0 for i in range(N)] for i in range(2)] # Traverse the string from the end for i in range(N - 1, -1, -1): # If i is equal to N - 1 if (i == N - 1): if (S[i] == '1'): dp[1][i] = 1 else: dp[0][i] = 1 # Otherwise, else: # Increment count of # substrings starting at i # and has 0 in the beginning if (S[i] == '0'): dp[0][i] = 1 + dp[1][i + 1] # Increment count of # substrings starting at i # and has 1 in the beginning else: dp[1][i] = 1 + dp[0][i + 1] # Stores the result ans = 0 # Iterate in the range [0, N-1] for i in range(N): # Update ans ans += max(dp[0][i], dp[1][i]) # Return the ans return ans # Driver code if __name__ == '__main__': # Given Input S = "0010" N = len(S) # Function call print (countAlternatingSubstrings(S, N)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to count number of alternating
// substrings from a given binary string
static int countAlternatingSubstrings(string S, int N)
{
// Initialize dp array, where dp[i][j] stores
// the number of alternating strings starts
// with i and having j elements.
int[,] dp = new int[2, N];
for(int i = 0; i < 2; i++)
{
for(int j = 0; j < N; j++)
{
dp[i, j] = 0;
}
}
// Traverse the string from the end
for(int i = N - 1; i >= 0; i--)
{
// If i is equal to N - 1
if (i == N - 1)
{
if (S[i] == '1')
dp[1, i] = 1;
else
dp[0, i] = 1;
}
// Otherwise,
else
{
// Increment count of
// substrings starting at i
// and has 0 in the beginning
if (S[i] == '0')
dp[0, i] = 1 + dp[1, i + 1];
// Increment count of
// substrings starting at i
// and has 1 in the beginning
else
dp[1, i] = 1 + dp[0, i + 1];
}
}
// Stores the result
int ans = 0;
// Iterate in the range [0, N-1]
for(int i = 0; i < N; i++)
{
// Update ans
ans += Math.Max(dp[0, i], dp[1, i]);
}
// Return the ans
return ans;
}
// Driver Code
public static void Main()
{
// Given Input
string S = "0010";
int N = S.Length;
// Function call
Console.Write(countAlternatingSubstrings(S, N));
}
}
// This code is contributed by target_2.
Javascript
<script>
// Javascript program for the above approach
// Function to count number of alternating
// substrings from a given binary string
function countAlternatingSubstrings(S, N)
{
// Initialize dp array, where dp[i][j] stores
// the number of alternating strings starts
// with i and having j elements.
var dp = new Array(2);
dp[0] = Array(N).fill(0);
dp[1] = Array(N).fill(0);
var i;
// Traverse the string from the end
for(i = N - 1; i >= 0; i--)
{
// If i is equal to N - 1
if (i == N - 1)
{
if (S[i] == '1')
dp[1][i] = 1;
else
dp[0][i] = 1;
}
// Otherwise,
else
{
// Increment count of
// substrings starting at i
// and has 0 in the beginning
if (S[i] == '0')
dp[0][i] = 1 + dp[1][i + 1];
// Increment count of
// substrings starting at i
// and has 1 in the beginning
else
dp[1][i] = 1 + dp[0][i + 1];
}
}
// Stores the result
var ans = 0;
// Iterate in the range [0, N-1]
for(i = 0; i < N; i++)
{
// Update ans
ans += Math.max(dp[0][i], dp[1][i]);
}
// Return the ans
return ans;
}
// Driver code
// Given Input
var S = "0010";
var N = S.length;
// Function call
document.write(countAlternatingSubstrings(S, N));
// This code is contributed by SURENDRA_GANGWAR
</script>
Producción:
7
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por pawanharwani11 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA