Dada una string S y un entero positivo K , la tarea es encontrar el número de subsecuencias “01” en la string generada por la concatenación de la string numérica dada S K veces .
Ejemplos:
Entrada: S = “0171”, K = 2
Salida: 6
Explicación:
La string formada por la concatenación de S, K número de veces es “01710171”. Hay un total de 6 posibles subsecuencias que están marcadas en negrita = {“ 01 710171″, “ 0 17 1 0171″, “ 0 1710 1 71″, “ 0 171017 1 “, “0171 01 71″, “0171 0 17 1 “ }.Entrada: S = “230013110087”, K = 2
Salida: 24
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar la string resultante concatenando S , K varias veces y luego encontrar todos los pares posibles (i, j) de la string tales que (i < j) y S[i ] = 0 y S[j] = 1 .
Complejidad de Tiempo: O((N*K) 2 )
Espacio Auxiliar: O(N*K)
Enfoque eficiente: la tarea también se puede optimizar observando los siguientes 2 casos:
- Caso 1: Substring «01» estrictamente dentro de cada ocurrencia de S en P . Supongamos que C es el conteo de ocurrencias de “01” en S , entonces en P sería C*K .
- Caso 2: Cuando ‘ 0 ‘ se encuentra dentro de la i -ésima ocurrencia de S y ‘ 1 ‘ se encuentra dentro de alguna j -ésima ocurrencia para formar una subsecuencia “ 01 ” tal que i < j, entonces encontrar el número de ocurrencias de “ 01 ” será lo mismo que elegir las dos strings o la aparición de strings en P dada por ((K)*(K – 1))/2 . Sea ese valor S i y S j y multiplíquelo por el número de ocurrencias de ‘0’ en S i (indicado por cnt0 ) y el número de ocurrencias de ‘1’ en S j (indicado porcnt1 ) da el número de subsecuencias de «01».
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 calculate the number of
// subsequences of "01"
int countSubsequence(string S, int N,
int K)
{
// Store count of 0's and 1's
int C = 0, C1 = 0, C0 = 0;
for (int i = 0; i < N; i++) {
if (S[i] == '1')
C1++;
else if (S[i] == '0')
C0++;
}
// Count of subsequences without
// concatenation
int B1 = 0;
for (int i = 0; i < N; i++) {
if (S[i] == '1')
B1++;
else if (S[i] == '0')
C = C + (C1 - B1);
}
// Case 1
int ans = C * K;
// Case 2
ans += (C1 * C0 * (((K) * (K - 1)) / 2));
// Return the total count
return ans;
}
// Driver Code
int main()
{
string S = "230013110087";
int K = 2;
int N = S.length();
cout << countSubsequence(S, N, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to calculate the number of
// subsequences of "01"
static int countSubsequence(String S, int N, int K)
{
// Store count of 0's and 1's
int C = 0, C1 = 0, C0 = 0;
for (int i = 0; i < N; i++) {
if (S.charAt(i) == '1')
C1++;
else if (S.charAt(i) == '0')
C0++;
}
// Count of subsequences without
// concatenation
int B1 = 0;
for (int i = 0; i < N; i++) {
if (S.charAt(i) == '1')
B1++;
else if (S.charAt(i) == '0')
C = C + (C1 - B1);
}
// Case 1
int ans = C * K;
// Case 2
ans += (C1 * C0 * (((K) * (K - 1)) / 2));
// Return the total count
return ans;
}
// Driver Code
public static void main(String[] args)
{
String S = "230013110087";
int K = 2;
int N = S.length();
System.out.println(countSubsequence(S, N, K));
}
}
// This code is contributed by Potta Lokesh
Python3
# python program for the above approach # Function to calculate the number of # subsequences of "01" def countSubsequence(S, N, K): # Store count of 0's and 1's C = 0 C1 = 0 C0 = 0 for i in range(0, N): if (S[i] == '1'): C1 += 1 elif (S[i] == '0'): C0 += 1 # Count of subsequences without # concatenation B1 = 0 for i in range(0, N): if (S[i] == '1'): B1 += 1 elif (S[i] == '0'): C = C + (C1 - B1) # Case 1 ans = C * K # Case 2 ans += (C1 * C0 * (((K) * (K - 1)) // 2)) # Return the total count return ans # Driver Code if __name__ == "__main__": S = "230013110087" K = 2 N = len(S) print(countSubsequence(S, N, K)) # This code is contributed by rakeshsahni
C#
// C# implementation for the above approach
using System;
class GFG
{
// Function to calculate the number of
// subsequences of "01"
static int countSubsequence(string S, int N, int K)
{
// Store count of 0's and 1's
int C = 0, C1 = 0, C0 = 0;
for (int i = 0; i < N; i++) {
if (S[i] == '1')
C1++;
else if (S[i] == '0')
C0++;
}
// Count of subsequences without
// concatenation
int B1 = 0;
for (int i = 0; i < N; i++) {
if (S[i] == '1')
B1++;
else if (S[i] == '0')
C = C + (C1 - B1);
}
// Case 1
int ans = C * K;
// Case 2
ans += (C1 * C0 * (((K) * (K - 1)) / 2));
// Return the total count
return ans;
}
// Driver Code
public static void Main()
{
string S = "230013110087";
int K = 2;
int N = S.Length;
Console.Write(countSubsequence(S, N, K));
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// Javascript program for the above approach
// Function to calculate the number of
// subsequences of "01"
function countSubsequence(S, N, K) {
// Store count of 0's and 1's
let C = 0,
C1 = 0,
C0 = 0;
for (let i = 0; i < N; i++) {
if (S[i] == "1") C1++;
else if (S[i] == "0") C0++;
}
// Count of subsequences without
// concatenation
let B1 = 0;
for (let i = 0; i < N; i++) {
if (S[i] == "1") B1++;
else if (S[i] == "0") C = C + (C1 - B1);
}
// Case 1
let ans = C * K;
// Case 2
ans += C1 * C0 * ((K * (K - 1)) / 2);
// Return the total count
return ans;
}
// Driver Code
let S = "230013110087";
let K = 2;
let N = S.length;
document.write(countSubsequence(S, N, K));
// This code is contributed by gfgking.
</script>
24
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por aniket173000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA