Dadas tres strings, ‘ X ‘, ‘ Y ‘ y ‘ Z ‘, la tarea es contar el número de subsecuencias de ‘ X ‘ que es lexicográficamente mayor o igual que ‘ Y ‘ y lexicográficamente menor o igual que ‘ Z ‘ .
Ejemplos:
Entrada: X = “abc”, Y = “a”, Z = “bc”
Salida: 6
Explicación: Las subsecuencias de X que son mayores o iguales a la string ‘Y’ y menores o iguales a la string ‘Z’ son
{ “a”, “b”, “ab”, “ac”, “bc”, “abc” }Entrada: X = “ade”, Y = “a”, Z = “dc”
Salida: 5
Explicación: Las subsecuencias de X que son mayores o iguales a la string ‘Y’ y menores o iguales a la string ‘Z’ son
{ “a”, “d”, “anuncio”, “ae”, “ade”}
Enfoque ingenuo: el enfoque más simple es generar todas las subsecuencias de la string ‘ X ‘ y verificar si es mayor o igual que ‘ Y ‘ y menor o igual que ‘ Z ‘.
Complejidad temporal: O(2 N * N)
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de la programación dinámica porque tiene subproblemas superpuestos y una subestructura óptima . Los subproblemas se pueden almacenar en la tabla dp[][][][] usando memoization donde dp[idx1][idx2][bound1][bound2] almacena la respuesta desde la posición idx1 de la string ‘ X ‘ hasta el final y desde la posición idx2 de la string ‘ Y ‘ y ‘ Z ‘ hasta el final, dondebound1 es una variable booleana que indica si la subsecuencia se construyó hasta idx1es igual a la substring correspondiente de ‘ Y ‘ hasta idx2 ybound2 es una variable booleana que indica si la subsecuencia construida hasta idx1 es igual a la substring correspondiente de ‘ Z ‘ hasta idx2 .
Siga los pasos a continuación para resolver el problema:
- Inicialice una array multidimensional global dp[100][100][2][2] con todos los valores como -1 que almacena el resultado de cada llamada recursiva.
- Defina una función recursiva, digamos countOfSubsequence(idx1, idx2,bound1,bound2) realizando los siguientes pasos.
- Si el valor de idx1 = Xsize ,
- Si idx2 = 0 , entonces la subsecuencia está vacía, por lo tanto, devuelve 0 .
- Sibound1 es false , entonces la subsecuencia es mayor que la string ‘Y’, por lo tanto, devuelve 1 .
- Si idx2 < Ysize , la subsecuencia es igual a la string ‘Y’ hasta idx2 – 1 , pero no completamente igual, por lo que devuelve 0 .
- Si el resultado del estado dp[idx1][idx2][bound1][bound2] ya se calculó, devuelva este valor dp[idx1][idx2][bound1][bound2] .
- En caso de que el elemento actual se excluya de la subsecuencia, llame recursivamente a la función countOfSubsequence para idx1 + 1 .
- Para incluir el elemento actual en idx1 de la string ‘ X ‘ en la subsecuencia, debemos verificar las restricciones tanto en la string ‘ Y ‘ como en la ‘ Z ‘,
- Para la string ‘ Y ‘,
- Sibound1 es falso , entonces el elemento actual se puede incluir ya que la subsecuencia ya es mayor que la string ‘ Y ‘ .
- De lo contrario, si idx2 >= Ysize , el elemento actual se puede incluir porque la subsecuencia ya es igual a la string ‘ Y ‘ y, además, se le agregan algunos caracteres más.
- De lo contrario, si X[idx1] >= Y[idx2] , al incluir el elemento actual, la subsecuencia actual es lexicográficamente mayor o igual que la string ‘ Y ‘ y, por lo tanto, se puede incluir.
- Si se cumple alguna de las tres condiciones anteriores, entonces es posible incluir el elemento actual wrt string ‘ Y ‘.
- Sibound1 es verdadero , verifique X[idx1] == Y[idx2 ] . Si X[idx1] > Y[idx2] , actualicebound1 a false .
- Para la string ‘ Z ‘,
- Sibound2 es falso , entonces el elemento actual puede incluirse ya que la subsecuencia ya es menor que la string ‘ Z ‘ .
- De lo contrario, si idx2 < Zsize y X[idx1] <= Z[idx2] , al incluir el elemento actual, la subsecuencia actual es lexicográficamente menor o igual que la string ‘ Z ‘ y, por lo tanto, se puede incluir.
- Si se cumple alguna de las dos condiciones anteriores, entonces es posible incluir el elemento actual wrt string ‘ Z ‘.
- Sibound2 es true , verifique X[idx1] == Z[idx2 ] . Si X[idx1] < Z[idx2] , actualicebound1 a false .
- Después de colocar el elemento actual en idx1 , llame recursivamente a la función countOfSubsequence (idx1 + 1, idx2 + 1) .
- Para la string ‘ Y ‘,
- Si el valor de idx1 = Xsize ,
- Imprime el valor devuelto por la función countOfSubsequence(0, 0, 1, 1) como resultado.
Ilustración:
X = “ca”
Y = «ab»
Z = “bc”
contar (0, 0, 1, 1)
/ (Excluir) \ Puede incluirse (X[0] == Y[0], X[0] < Z[0])
/ \ limite1 = 1, limite2 = 0 (como X[0] < Z[0] )
cuenta(1, 0, 1, 1) cuenta(1, 1, 1, 0)
/ (Excluir) \ No se puede incluir / (Excluir) \ Se puede incluir (X[1] > Y[1], X[1] == Z[1])
/ \ X[1] > Y[0] / \bound1 = 0 (como X[1] > Y[1])
/\pero X[1] > Z[0]/\bound2 = 0 (como antes también era 0)
Devuelve ‘0’ [“”] Devuelve ‘0’ [“c”] Devuelve ‘0’ [“a”] Devuelve ‘1’ [“ac”]
subsecuencia vacía [bound1 = 1, [bound1 = 0]
[idx2 == 0] pero idx2 <Tamaño Y()]
Por lo tanto, la respuesta final es 1 , es decir, «ac».
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;
int dp[100][100][2][2];
string X, Y, Z;
int XSize, YSize, ZSize;
// Function to find the count
// of subsequences of 'X' which
// is greater than or equal to 'Y'
// but lesser than or equal to 'Z'.
int countOfSubsequence(
int idx1, int idx2,
bool bound1, bool bound2)
{
// If the string 'X'
// is traversed completely.
if (idx1 == XSize) {
// If subsequence is empty, return 0.
if (idx2 == 0)
return 0;
// If bound1 is false (current subsequence
// is larger than 'Y') or
// idx2 is greater than or
// equal to Ysize, return 1.
if (!bound1 or idx2 >= YSize)
return 1;
// Else return 0.
return 0;
}
// If the state has already
// been computed, return it.
if (dp[idx1][idx2][bound1][bound2] != -1) {
return dp[idx1][idx2][bound1][bound2];
}
// Exclude the current element
// from the subsequence.
int ans = countOfSubsequence(
idx1 + 1, idx2,
bound1, bound2);
// Variable to check if current
// character can be included
// the subsequence by checking
// the strings 'Y' and 'Z'.
int isOk = 0;
// Check for first string
// If bound1 is false,
// it means the current character
// can be included in the
// subsequence as the current
// subsequence is already
// greater than the string 'Y'.
if (!bound1) {
++isOk;
}
// If idx2 >= Ysize,
// the subsequence formed by placing
// current character is of greater length
// than string 'Y', hence can be placed.
// If current character is greater than
// or equal to the corresponding
// character in string 'Y', it can be placed.
else if (idx2 >= YSize or X[idx1] >= Y[idx2]) {
++isOk;
bound1 &= (idx2 < YSize
and X[idx1] == Y[idx2]);
}
// Check for second string
// If bound2 is false,
// it means the current character
// can be included in the subsequence
// as the current subsequence is already
// lesser than the string 'Z'.
if (!bound2) {
++isOk;
}
// If current character is lesser than
// or equal to the corresponding character
// in string 'Z', it can be placed.
else if (idx2 < ZSize
and X[idx1] <= Z[idx2]) {
++isOk;
bound2 &= (X[idx1] == Z[idx2]);
}
// If constraints are met by both string
// 'Y' and 'Z', it is possible to include
// the current character of
// string 'X' in the subsequence.
if (isOk == 2) {
// Increase both idx1 and idx2 by 1.
ans += countOfSubsequence(
idx1 + 1, idx2 + 1,
bound1, bound2);
}
// Return the answer.
return dp[idx1][idx2][bound1][bound2] = ans;
}
// Utility function to find the count
// of subsequences of 'X' which is
// greater than or equal to 'Y'
// but lesser than or equal to 'Z'.
int UtilCountOfSubsequence()
{
// Initialize the dp array with -1.
memset(dp, -1, sizeof dp);
// Calculate the size of strings
//'X', 'Y', and 'Z'.
XSize = X.size();
YSize = Y.size();
ZSize = Z.size();
// Function call
return countOfSubsequence(0, 0, 1, 1);
}
// Driver code
int main()
{
// Input strings 'X', 'Y' and 'Z'.
X = "abc";
Y = "a";
Z = "bc";
// If string 'Y' is greater
// than string 'Z', return 0.
if (Y > Z) {
cout << 0 << endl;
return 0;
}
cout << UtilCountOfSubsequence()
<< endl;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
static int [][][][] dp = new int[100][100][2][2];
static String X, Y, Z;
static int XSize, YSize, ZSize;
// Function to find the count
// of subsequences of 'X' which
// is greater than or equal to 'Y'
// but lesser than or equal to 'Z'.
static int countOfSubsequence(int idx1, int idx2,Boolean bound1, Boolean bound2)
{
// If the string 'X'
// is traversed completely.
if (idx1 == XSize) {
// If subsequence is empty, return 0.
if (idx2 == 0)
return 0;
// If bound1 is false (current subsequence
// is larger than 'Y') or
// idx2 is greater than or
// equal to Ysize, return 1.
if (!bound1 || idx2 >= YSize)
return 1;
// Else return 0.
return 0;
}
// If the state has already
// been computed, return it.
if (dp[idx1][idx2][bound1?1:0][bound2?1:0] != -1) {
return dp[idx1][idx2][bound1?1:0][bound2?1:0];
}
// Exclude the current element
// from the subsequence.
int ans = countOfSubsequence(idx1 + 1, idx2, bound1, bound2);
// Variable to check if current
// character can be included
// the subsequence by checking
// the strings 'Y' and 'Z'.
int isOk = 0;
// Check for first string
// If bound1 is false,
// it means the current character
// can be included in the
// subsequence as the current
// subsequence is already
// greater than the string 'Y'.
if (bound1 == false) {
++isOk;
}
// If idx2 >= Ysize,
// the subsequence formed by placing
// current character is of greater length
// than string 'Y', hence can be placed.
// If current character is greater than
// or equal to the corresponding
// character in string 'Y', it can be placed.
else if (idx2 >= YSize || (int)X.charAt(idx1) >= (int)Y.charAt(idx2)) {
++isOk;
bound1 &= (idx2 < YSize && X.charAt(idx1) == Y.charAt(idx2));
}
// Check for second string
// If bound2 is false,
// it means the current character
// can be included in the subsequence
// as the current subsequence is already
// lesser than the string 'Z'.
if (!bound2) {
++isOk;
}
// If current character is lesser than
// or equal to the corresponding character
// in string 'Z', it can be placed.
else if (idx2 < ZSize && (int)X.charAt(idx1) <= (int)Z.charAt(idx2)) {
++isOk;
bound2 &= (X.charAt(idx1) == Z.charAt(idx2));
}
// If constraints are met by both string
// 'Y' and 'Z', it is possible to include
// the current character of
// string 'X' in the subsequence.
if (isOk == 2) {
// Increase both idx1 and idx2 by 1.
ans += countOfSubsequence(idx1 + 1, idx2 + 1, bound1, bound2);
}
// Return the answer.
return dp[idx1][idx2][bound1?1:0][bound2?1:0] = ans;
}
// Utility function to find the count
// of subsequences of 'X' which is
// greater than or equal to 'Y'
// but lesser than or equal to 'Z'.
static int UtilCountOfSubsequence()
{
// Initialize the dp array with -1.
for(int i=0;i<100;i++){
for(int j=0;j<100;j++){
for(int k=0;k<2;k++){
for(int l=0;l<2;l++){
dp[i][j][k][l] = -1;
}
}
}
}
// Calculate the size of strings
//'X', 'Y', and 'Z'.
XSize = X.length();
YSize = Y.length();
ZSize = Z.length();
// Function call
return countOfSubsequence(0, 0, true , true);
}
// Driver code
public static void main(String args[])
{
// Input strings 'X', 'Y' and 'Z'.
X = "abc";
Y = "a";
Z = "bc";
// If string 'Y' is greater
// than string 'Z', return 0.
if (Y.compareTo(Z) > 0) {
System.out.println(0);
return;
}
System.out.println(UtilCountOfSubsequence());
}
}
// This code is contributed by shinjanpatra
Python3
# Python3 code for the above approach dp = [None] * 100 for i in range(len(dp)): dp[i] = [None] * 100 for j in range(len(dp[i])): dp[i][j] = [None, None] for k in range(len(dp[i][j])): dp[i][j][k] = [-1, -1] X, Y, Z = 0, 0, 0 XSize, YSize, ZSize = 0, 0, 0 # Function to find the count # of subsequences of 'X' which # is greater than or equal to 'Y' # but lesser than or equal to 'Z'. def countOfSubsequence(idx1, idx2, bound1, bound2): global X, Y, Z, XSize, YSize, ZSize, dp # If the string 'X' # is traversed completely. if (idx1 == XSize): # If subsequence is empty, return 0. if (idx2 == 0): return 0 # If bound1 is false (current subsequence # is larger than 'Y') or # idx2 is greater than or # equal to Ysize, return 1. if (not bound1 or idx2 >= YSize): return 1 # Else return 0. return 0 # If the state has already # been computed, return it. if (dp[idx1][idx2][bound1][bound2] != -1): return dp[idx1][idx2][bound1][bound2] # Exclude the current element # from the subsequence. ans = countOfSubsequence(idx1 + 1, idx2, bound1, bound2) # Variable to check if current # character can be included # the subsequence by checking # the strings 'Y' and 'Z'. isOk = 0 # Check for first string # If bound1 is false, # it means the current character # can be included in the # subsequence as the current # subsequence is already # greater than the string 'Y'. if (not bound1): isOk += 1 # If idx2 >= Ysize, # the subsequence formed by placing # current character is of greater length # than string 'Y', hence can be placed. # If current character is greater than # or equal to the corresponding # character in string 'Y', it can be placed. elif (idx2 >= YSize or X[idx1] >= Y[idx2]): isOk += 1 bound1 &= (idx2 < YSize and X[idx1] == Y[idx2]) # Check for second string # If bound2 is false, # it means the current character # can be included in the subsequence # as the current subsequence is already # lesser than the string 'Z'. if (not bound2): isOk += 1 # If current character is lesser than # or equal to the corresponding character # in string 'Z', it can be placed. elif (idx2 < ZSize and X[idx1] <= Z[idx2]): isOk += 1 bound2 &= (X[idx1] == Z[idx2]) # If constraints are met by both string # 'Y' && 'Z', it is possible to include # the current character of # string 'X' in the subsequence. if (isOk == 2): # Increase both idx1 && idx2 by 1. ans += countOfSubsequence(idx1 + 1, idx2 + 1, bound1, bound2) # Return the answer. dp[idx1][idx2][bound1][bound2] = ans return ans # Utility function to find the count # of subsequences of 'X' which is # greater than or equal to 'Y' # but lesser than or equal to 'Z'. def UtilCountOfSubsequence(): global X, Y, Z, XSize, YSize, ZSize, dp # Calculate the size of strings # 'X', 'Y', and 'Z'. XSize = len(X) YSize = len(Y) ZSize = len(Z) # Function call return countOfSubsequence(0, 0, 1, 1) # Driver code # Input strings 'X', 'Y' and 'Z'. X = "abc" Y = "a" Z = "bc" # If string 'Y' is greater # than string 'Z', return 0. if (Y > Z): print(0) print(UtilCountOfSubsequence()) # This code is contributed by phasing17
C#
// C# program to implement above approach
using System;
using System.Collections.Generic;
class GFG
{
public static int[, , ,] dp = new int[100, 100, 2, 2];
public static String X = "", Y = "", Z = "";
public static int XSize, YSize, ZSize;
// Return 1 if bool is true
// else false
public static int boolToInt(bool input){
if(input) return 1;
return 0;
}
// Function to find the count
// of subsequences of 'X' which
// is greater than or equal to 'Y'
// but lesser than or equal to 'Z'.
public static int countOfSubsequence(int idx1, int idx2, bool bound1, bool bound2)
{
// If the string 'X'
// is traversed completely.
if (idx1 == XSize) {
// If subsequence is empty, return 0.
if (idx2 == 0)
return 0;
// If bound1 is false (current subsequence
// is larger than 'Y') or
// idx2 is greater than or
// equal to Ysize, return 1.
if (!bound1 || idx2 >= YSize)
return 1;
// Else return 0.
return 0;
}
// If the state has already
// been computed, return it.
if (dp[idx1, idx2, boolToInt(bound1), boolToInt(bound2)] != -1) {
return dp[idx1, idx2, boolToInt(bound1), boolToInt(bound2)];
}
// Exclude the current element
// from the subsequence.
int ans = countOfSubsequence(idx1 + 1, idx2, bound1, bound2);
// Variable to check if current
// character can be included
// the subsequence by checking
// the strings 'Y' and 'Z'.
int isOk = 0;
// Check for first string
// If bound1 is false,
// it means the current character
// can be included in the
// subsequence as the current
// subsequence is already
// greater than the string 'Y'.
if (!bound1) {
++isOk;
}
// If idx2 >= Ysize,
// the subsequence formed by placing
// current character is of greater length
// than string 'Y', hence can be placed.
// If current character is greater than
// or equal to the corresponding
// character in string 'Y', it can be placed.
else if (idx2 >= YSize || X[idx1] >= Y[idx2]){
++isOk;
bound1 &= (idx2 < YSize && X[idx1] == Y[idx2]);
}
// Check for second string
// If bound2 is false,
// it means the current character
// can be included in the subsequence
// as the current subsequence is already
// lesser than the string 'Z'.
if (!bound2) {
++isOk;
}
// If current character is lesser than
// or equal to the corresponding character
// in string 'Z', it can be placed.
else if (idx2 < ZSize && X[idx1] <= Z[idx2]) {
++isOk;
bound2 &= (X[idx1] == Z[idx2]);
}
// If constraints are met by both string
// 'Y' and 'Z', it is possible to include
// the current character of
// string 'X' in the subsequence.
if (isOk == 2) {
// Increase both idx1 and idx2 by 1.
ans += countOfSubsequence(idx1 + 1, idx2 + 1, bound1, bound2);
}
// Return the answer.
return dp[idx1, idx2, boolToInt(bound1), boolToInt(bound2)] = ans;
}
// Utility function to find the count
// of subsequences of 'X' which is
// greater than or equal to 'Y'
// but lesser than or equal to 'Z'.
public static int UtilCountOfSubsequence()
{
// Initialize the dp array with -1.
for(int i=0 ; i<100 ; i++){
for(int j=0 ; j<100 ; j++){
for(int k=0 ; k<2 ; k++){
for(int l=0 ; l<2 ; l++){
dp[i, j, k, l] = -1;
}
}
}
}
// Calculate the size of strings
//'X', 'Y', and 'Z'.
XSize = X.Length;
YSize = Y.Length;
ZSize = Z.Length;
// Function call
return countOfSubsequence(0, 0, true, true);
}
// Driver Code
public static void Main(string[] args){
// Input strings 'X', 'Y' and 'Z'.
X = "abc";
Y = "a";
Z = "bc";
// If string 'Y' is greater
// than string 'Z', return 0.
if (Y.CompareTo(Z) > 0) {
Console.Write(0);
return;
}
Console.Write(UtilCountOfSubsequence());
}
}
// This code is contributed by subhamgoyal2014.
Javascript
<script>
// JavaScript code for the above approach
let dp = new Array(100);
for (let i = 0; i < dp.length; i++) {
dp[i] = new Array(100)
for (let j = 0; j < dp[i].length; j++) {
dp[i][j] = new Array(2)
for (let k = 0; k < dp[i][j].length; k++) {
dp[i][j][k] = new Array(2).fill(-1)
}
}
}
let X, Y, Z;
let XSize, YSize, ZSize;
// Function to find the count
// of subsequences of 'X' which
// is greater than or equal to 'Y'
// but lesser than or equal to 'Z'.
function countOfSubsequence(
idx1, idx2,
bound1, bound2) {
// If the string 'X'
// is traversed completely.
if (idx1 == XSize) {
// If subsequence is empty, return 0.
if (idx2 == 0)
return 0;
// If bound1 is false (current subsequence
// is larger than 'Y') or
// idx2 is greater than or
// equal to Ysize, return 1.
if (!bound1 || idx2 >= YSize)
return 1;
// Else return 0.
return 0;
}
// If the state has already
// been computed, return it.
if (dp[idx1][idx2][bound1][bound2] != -1) {
return dp[idx1][idx2][bound1][bound2];
}
// Exclude the current element
// from the subsequence.
let ans = countOfSubsequence(
idx1 + 1, idx2,
bound1, bound2);
// Variable to check if current
// character can be included
// the subsequence by checking
// the strings 'Y' and 'Z'.
let isOk = 0;
// Check for first string
// If bound1 is false,
// it means the current character
// can be included in the
// subsequence as the current
// subsequence is already
// greater than the string 'Y'.
if (!bound1) {
++isOk;
}
// If idx2 >= Ysize,
// the subsequence formed by placing
// current character is of greater length
// than string 'Y', hence can be placed.
// If current character is greater than
// or equal to the corresponding
// character in string 'Y', it can be placed.
else if (idx2 >= YSize || X[idx1] >= Y[idx2]) {
++isOk;
bound1 &= (idx2 < YSize
&& X[idx1] == Y[idx2]);
}
// Check for second string
// If bound2 is false,
// it means the current character
// can be included in the subsequence
// as the current subsequence is already
// lesser than the string 'Z'.
if (!bound2) {
++isOk;
}
// If current character is lesser than
// or equal to the corresponding character
// in string 'Z', it can be placed.
else if (idx2 < ZSize
&& X[idx1] <= Z[idx2]) {
++isOk;
bound2 &= (X[idx1] == Z[idx2]);
}
// If constraints are met by both string
// 'Y' && 'Z', it is possible to include
// the current character of
// string 'X' in the subsequence.
if (isOk == 2) {
// Increase both idx1 && idx2 by 1.
ans += countOfSubsequence(
idx1 + 1, idx2 + 1,
bound1, bound2);
}
// Return the answer.
return dp[idx1][idx2][bound1][bound2] = ans;
}
// Utility function to find the count
// of subsequences of 'X' which is
// greater than or equal to 'Y'
// but lesser than or equal to 'Z'.
function UtilCountOfSubsequence() {
// Calculate the size of strings
//'X', 'Y', and 'Z'.
XSize = X.length;
YSize = Y.length;
ZSize = Z.length;
// Function call
return countOfSubsequence(0, 0, 1, 1);
}
// Driver code
// Input strings 'X', 'Y' and 'Z'.
X = "abc";
Y = "a";
Z = "bc";
// If string 'Y' is greater
// than string 'Z', return 0.
if (Y > Z) {
document.write(0 + '<br>')
}
document.write(UtilCountOfSubsequence()
+ '<br>')
// This code is contributed by Potta Lokesh
</script>
Producción
6
Complejidad de Tiempo: O(N 2 * 2 * 2)
Espacio Auxiliar: O(N 2 * 2 * 2)
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA