Dada una string, encuentre el recuento de distintas subsecuencias de la misma.
Ejemplos:
Input : str = "gfg" Output : 7 The seven distinct subsequences are "", "g", "f", "gf", "fg", "gg" and "gfg" Input : str = "ggg" Output : 4 The four distinct subsequences are "", "g", "gg" and "ggg"
El problema de contar subsecuencias distintas es fácil si todos los caracteres de la string de entrada son distintos. La cuenta es igual a n C 0 + n C 1 + n C 2 + … n C n = 2 n .
¿Cómo contar subsecuencias distintas cuando puede haber repetición en la string de entrada?
Una solución simple para contar distintas subsecuencias en una string con duplicados es generar todas las subsecuencias. Para cada subsecuencia, guárdela en una tabla hash si aún no existe. La complejidad temporal de esta solución es exponencial y requiere espacio adicional exponencial.
Método 1 (enfoque ingenuo): uso de un conjunto (sin programación dinámica)
Enfoque: Generar todas las subsecuencias posibles de una string dada. Las subsecuencias de una string se pueden generar de la siguiente manera:
- Incluya un elemento particular (digamos i th ) en la array de salida y llame recursivamente a la función para el resto de la string de entrada. Esto da como resultado las subsecuencias de una string que tiene i -ésimo carácter.
- Excluya un elemento en particular (digamos i th ) y llame recursivamente a la función para el resto de la string de entrada. Este contiene todas las subsecuencias que no tienen el i -ésimo carácter.
Una vez que hemos generado una subsecuencia, en el caso base de la función insertamos esa subsecuencia generada en un conjunto desordenado. Un conjunto desordenado es una estructura de datos que almacena distintos elementos de manera desordenada. De esta manera, insertamos todas las subsecuencias generadas en el conjunto e imprimimos el tamaño del conjunto como nuestra respuesta porque, al final, el conjunto contendrá solo subsecuencias distintas.
Implementación:
C++
// C++ program to print distinct
// subsequences of a given string
#include <bits/stdc++.h>
using namespace std;
// Create an empty set to store the subsequences
unordered_set<string> sn;
// Function for generating the subsequences
void subsequences(char s[], char op[], int i, int j)
{
// Base Case
if (s[i] == '\0') {
op[j] = '\0';
// Insert each generated
// subsequence into the set
sn.insert(op);
return;
}
// Recursive Case
else {
// When a particular character is taken
op[j] = s[i];
subsequences(s, op, i + 1, j + 1);
// When a particular character isn't taken
subsequences(s, op, i + 1, j);
return;
}
}
// Driver Code
int main()
{
char str[] = "ggg";
int m = sizeof(str) / sizeof(char);
int n = pow(2, m) + 1;
// Output array for storing
// the generating subsequences
// in each call
char op[m+1]; //extra one for having \0 at the end
// Function Call
subsequences(str, op, 0, 0);
// Output will be the number
// of elements in the set
cout << sn.size();
sn.clear();
return 0;
// This code is contributed by Kishan Mishra
}
Python3
# Python3 program to print # distinct subsequences of # a given string import math # Create an empty set # to store the subsequences sn = [] global m m = 0 # Function for generating # the subsequences def subsequences(s, op, i, j): # Base Case if(i == m): op[j] = None temp = "".join([i for i in op if i]) # Insert each generated # subsequence into the set sn.append(temp) return # Recursive Case else: # When a particular # character is taken op[j] = s[i] subsequences(s, op, i + 1, j + 1) # When a particular # character isn't taken subsequences(s, op, i + 1, j) return # Driver Code str = "ggg" m = len(str) n = int(math.pow(2, m) + 1) # Output array for storing # the generating subsequences # in each call op = [None for i in range(n)] # Function Call subsequences(str, op, 0, 0) # Output will be the number # of elements in the set print(len(set(sn))) # This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript program to print distinct
// subsequences of a given string
// Create an empty set to store the subsequences
let sn = new Set();
let m = 0;
// Function for generating the subsequences
function subsequences(s, op, i, j)
{
// Base Case
if (i == m) {
op[j] = '\0';
// Insert each generated
// subsequence into the set
sn.add(op.join(""));
return;
}
// Recursive Case
else
{
// When a particular character is taken
op[j] = s[i];
subsequences(s, op, i + 1, j + 1);
// When a particular character isn't taken
subsequences(s, op, i + 1, j);
return;
}
}
// Driver Code
let str= "ggg";
m = str.length;
let n = Math.pow(2, m) + 1;
// Output array for storing
// the generating subsequences
// in each call
let op=new Array(n);
// Function Call
subsequences(str, op, 0, 0);
// Output will be the number
// of elements in the set
document.write(sn.size);
// This code is contributed by patel2127
</script>
Producción
4
Complejidad de tiempo : O(2^n)
Espacio auxiliar: O(n)
donde n es la longitud de la string.
Método 2 (enfoque eficiente): uso de programación dinámica
Una Solución Eficiente no requiere la generación de subsecuencias.
Let countSub(n) be count of subsequences of first n characters in input string. We can recursively write it as below. countSub(n) = 2*Count(n-1) - Repetition If current character, i.e., str[n-1] of str has not appeared before, then Repetition = 0 Else: Repetition = Count(m) Here m is index of previous occurrence of current character. We basically remove all counts ending with previous occurrence of current character.
¿Como funciona esto?
Si no hay repeticiones, el conteo se convierte en el doble del conteo para n-1 porque obtenemos el conteo (n-1) más subsecuencias al agregar el carácter actual al final de todas las subsecuencias posibles con n-1 longitud.
Si hay repeticiones, encontramos un recuento de todas las subsecuencias distintas que terminan con la aparición anterior. Este recuento se puede obtener llamando recursivamente a un índice de la aparición anterior.
Dado que la recurrencia anterior tiene subproblemas superpuestos, podemos resolverlo usando Programación Dinámica.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to count number of distinct
// subsequences of a given string.
#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 256;
// Returns count of distinct subsequences of str.
int countSub(string str)
{
// Create an array to store index
// of last
vector<int> last(MAX_CHAR, -1);
// Length of input string
int n = str.length();
// dp[i] is going to store count of distinct
// subsequences of length i.
int dp[n + 1];
// Empty substring has only one subsequence
dp[0] = 1;
// Traverse through all lengths from 1 to n.
for (int i = 1; i <= n; i++) {
// Number of subsequences with substring
// str[0..i-1]
dp[i] = 2 * dp[i - 1];
// If current character has appeared
// before, then remove all subsequences
// ending with previous occurrence.
if (last[str[i - 1]] != -1)
dp[i] = dp[i] - dp[last[str[i - 1]]];
// Mark occurrence of current character
last[str[i - 1]] = (i - 1);
}
return dp[n];
}
// Driver code
int main()
{
cout << countSub("gfg");
return 0;
}
Java
// Java program to count number of distinct
// subsequences of a given string.
import java.util.ArrayList;
import java.util.Arrays;
public class Count_Subsequences {
static final int MAX_CHAR = 256;
// Returns count of distinct subsequences of str.
static int countSub(String str)
{
// Create an array to store index
// of last
int[] last = new int[MAX_CHAR];
Arrays.fill(last, -1);
// Length of input string
int n = str.length();
// dp[i] is going to store count of distinct
// subsequences of length i.
int[] dp = new int[n + 1];
// Empty substring has only one subsequence
dp[0] = 1;
// Traverse through all lengths from 1 to n.
for (int i = 1; i <= n; i++) {
// Number of subsequences with substring
// str[0..i-1]
dp[i] = 2 * dp[i - 1];
// If current character has appeared
// before, then remove all subsequences
// ending with previous occurrence.
if (last[(int)str.charAt(i - 1)] != -1)
dp[i] = dp[i] - dp[last[(int)str.charAt(i - 1)]];
// Mark occurrence of current character
last[(int)str.charAt(i - 1)] = (i - 1);
}
return dp[n];
}
// Driver code
public static void main(String args[])
{
System.out.println(countSub("gfg"));
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python3 program to count number of
# distinct subsequences of a given string
MAX_CHAR = 256
def countSub(ss):
# create an array to store index of last
last = [-1 for i in range(MAX_CHAR + 1)]
# length of input string
n = len(ss)
# dp[i] is going to store count of
# discount subsequence of length of i
dp = [-2 for i in range(n + 1)]
# empty substring has only
# one subsequence
dp[0] = 1
# Traverse through all lengths
# from 1 to n
for i in range(1, n + 1):
# number of subsequence with
# substring str[0...i-1]
dp[i] = 2 * dp[i - 1]
# if current character has appeared
# before, then remove all subsequences
# ending with previous occurrence.
if last[ord(ss[i - 1])] != -1:
dp[i] = dp[i] - dp[last[ord(ss[i - 1])]]
last[ord(ss[i - 1])] = i - 1
return dp[n]
# Driver code
print(countSub("gfg"))
# This code is contributed
# by mohit kumar 29
C#
// C# program to count number of distinct
// subsequences of a given string.
using System;
public class Count_Subsequences {
static readonly int MAX_CHAR = 256;
// Returns count of distinct subsequences of str.
static int countSub(String str)
{
// Create an array to store index
// of last
int[] last = new int[MAX_CHAR];
for (int i = 0; i < MAX_CHAR; i++)
last[i] = -1;
// Length of input string
int n = str.Length;
// dp[i] is going to store count of
// distinct subsequences of length i.
int[] dp = new int[n + 1];
// Empty substring has only one subsequence
dp[0] = 1;
// Traverse through all lengths from 1 to n.
for (int i = 1; i <= n; i++) {
// Number of subsequences with substring
// str[0..i-1]
dp[i] = 2 * dp[i - 1];
// If current character has appeared
// before, then remove all subsequences
// ending with previous occurrence.
if (last[(int)str[i - 1]] != -1)
dp[i] = dp[i] - dp[last[(int)str[i - 1]]];
// Mark occurrence of current character
last[(int)str[i - 1]] = (i - 1);
}
return dp[n];
}
// Driver code
public static void Main(String[] args)
{
Console.WriteLine(countSub("gfg"));
}
}
// This code is contributed 29AjayKumar
Javascript
<script>
// Javascript program to count number of
// distinct subsequences of a given string.
let MAX_CHAR = 256;
// Returns count of distinct subsequences
// of str.
function countSub(str)
{
// Create an array to store index
// of last
let last = new Array(MAX_CHAR);
last.fill(-1);
// Length of input string
let n = str.length;
// dp[i] is going to store count of distinct
// subsequences of length i.
let dp = new Array(n + 1);
// Empty substring has only one subsequence
dp[0] = 1;
// Traverse through all lengths from 1 to n.
for(let i = 1; i <= n; i++)
{
// Number of subsequences with substring
// str[0..i-1]
dp[i] = 2 * dp[i - 1];
// If current character has appeared
// before, then remove all subsequences
// ending with previous occurrence.
if (last[str[i - 1].charCodeAt()] != -1)
dp[i] = dp[i] - dp[last[str[i - 1].charCodeAt()]];
// Mark occurrence of current character
last[str[i - 1].charCodeAt()] = (i - 1);
}
return dp[n];
}
// Driver code
document.write(countSub("gfg"));
// This code is contributed by mukesh07
</script>
Producción
7
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Método 3: sin espacio extra
Digamos que tenemos 2 variables: `allCount` que suma el recuento total de subsecuencias distintas y `levelCount` que almacena el recuento de subsecuencias que terminan en el índice i. Para encontrar repeticiones almacenaremos el levelCount más reciente para cada carácter. Finalmente veremos cómo podemos determinar `allCount` usando la variable `levelCount`.
Aquí hay una representación de la declaración anterior:
Di s = «abab»
Inicialicemos todos los caracteres de string en un mapa con -1. El valor en este mapa representa cuántas subsecuencias distintas terminaron en la última aparición de este carácter.
mapa = {a:-1,b:-1}
También inicialmente tenemos
cuentanivel=0;
todosCuenta = 0;
Ahora iterando a través de cada carácter
- 1ra iteración ‘a’
- Las distintas subsecuencias que terminan en ‘a’ son: “a”. Entonces hacemos levelCount = 1, también allCount es 1 ahora.
el mapa se actualizará como map[`current_char`]=levelCount. - cuentanivel = 1; todosCuenta = 1; mapa = {a:1,b:-1}
- Las distintas subsecuencias que terminan en ‘a’ son: “a”. Entonces hacemos levelCount = 1, también allCount es 1 ahora.
- 2da iteración ‘b’
- Las distintas subsecuencias que terminan en ‘b’ son “ab”,”b”. Así que levelCount = 2.
- También las subsecuencias totales que encontramos hasta ahora son 3. allCount = 3.
- Aquí podemos notar que levelCount se puede determinar a partir del último valor de la variable allCount añadiéndole 1
- levelCount = allCount+1 (levelCount= 1+1=2)
- En caso de que se trate de un carácter distinto, el allCount actual también se puede determinar fácilmente como
- allCount = allCount + levelCount; (todoCuenta= 1+ 2 = 3)
- También actualizamos el mapa con el levelCount del personaje actual. mapa{a:1,b:2}
- 3ra iteración ‘a’
- Ahora tenemos una repetición.
- Las distintas subsecuencias que terminan en ‘a’ ahora son “aa”,”ba”,”aba”,”a”. Así que nuestro levelCount ahora es 4: que se determina como se indicó anteriormente allCount+1 = 3+1 = 4.
- si este fuera un carácter distinto, allcount habría sido 7 (allCount = allCount+levelCount = 3+4) pero tendremos que eliminar la repetición, que es map.get(`a`) que es 1, por lo que ahora allCount es 7- 1 = 6
- Aquí tenga en cuenta que esencialmente hemos eliminado los resultados de nuestra primera iteración, que era la subsecuencia duplicada «a». Esto simplemente significa que podemos formar las mismas subsecuencias que terminan con nuestra nueva `a` fundada que se habría formado la antigua `a`, por lo que restamos las subsecuencias más antiguas.
- el mapa ahora se actualiza con un nuevo nivelContador de a a {a:4,b:2}
- En caso de repetición, el cálculo de allCount cambia como
- allCount = allCount + levelCount – map.get(currentCharacter);
- todosCuenta = 3+4-1 = 6
- 4ta iteración ‘b’
- De nuevo una repetición.
- Las subsecuencias que terminan con ‘b’ ahora son «abb», «bb», «aab», «bab», «abab», «ab» , «b» cuyo recuento es el mismo que levelCount = allCount+1 = 6+1 = 7 .
- allCount será = allCount+levelCount – map.get(‘b’) = 6+7-2 = 11
- El número total de subsecuencias distintas es allCount.
- Si también se incluye una string vacía, nuestra respuesta es allCount+1.
- A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Returns count of distinct
// subsequences of str.
int countSub(string s)
{
map<char, int> Map;
// Iterate from 0 to s.length()
for(int i = 0; i < s.length(); i++)
{
Map[s[i]] = -1;
}
int allCount = 0;
int levelCount = 0;
// Iterate from 0 to s.length()
for(int i = 0; i < s.length(); i++)
{
char c = s[i];
// Check if i equal to 0
if (i == 0)
{
allCount = 1;
Map = 1;
levelCount = 1;
continue;
}
// Replace levelCount with
// allCount + 1
levelCount = allCount + 1;
// If map is less than 0
if (Map < 0)
{
allCount = allCount + levelCount;
}
else
{
allCount = allCount +
levelCount - Map;
}
Map = levelCount;
}
// Return answer
return allCount;
}
// Driver code
int main()
{
string list[] = { "abab", "gfg" };
for(string s : list)
{
int cnt = countSub(s);
int withEmptyString = cnt + 1;
cout << "With empty string count for "
<< s << " is " << withEmptyString
<< endl;
cout << "Without empty string count for "
<< s << " is " << cnt << endl;
}
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java Program for above approach
import java.io.*;
import java.util.*;
class SubsequenceCount
{
// Returns count of distinct
// subsequences of str.
public static int countSub(String s)
{
HashMap<Character,
Integer> map = new HashMap<Character,
Integer>();
// Iterate from 0 to s.length()
for(int i = 0; i < s.length(); i++)
{
map.put(s.charAt(i), -1);
}
int allCount = 0;
int levelCount = 0;
// Iterate from 0 to s.length()
for(int i=0;i<s.length();i++)
{
char c = s.charAt(i);
// Check if i equal to 0
if(i==0)
{
allCount = 1;
map.put(c,1);
levelCount = 1;
continue;
}
// Replace levelCount with
// allCount + 1
levelCount = allCount + 1;
// If map is less than 0
if(map.get(c)<0)
{
allCount = allCount + levelCount;
}
else
{
allCount = allCount + levelCount - map.get(c);
}
map.put(c,levelCount);
}
// Return answer
return allCount;
}
// Driver Code
public static void main(String[] args)
{
List<String> list = Arrays.asList("abab","gfg");
for(String s : list)
{
int cnt = countSub(s);
int withEmptyString = cnt+1;
System.out.println("With empty string count for " +
s +" is " + withEmptyString);
System.out.println("Without empty string count for " +
s + " is " + cnt);
}
}
}
//Code is contributed by abhisht7
Python3
# Python3 program for above approach
# Returns count of distinct
# subsequences of str.
def countSub(s):
Map = {}
# Iterate from 0 to length of s
for i in range(len(s)):
Map[s[i]] = -1
allCount = 0
levelCount = 0
# Iterate from 0 to length of s
for i in range(len(s)):
c = s[i]
# Check if i equal to 0
if (i == 0):
allCount = 1
Map= 1
levelCount = 1
continue
# Replace levelCount with
# allCount + 1
levelCount = allCount + 1
# If map is less than 0
if (Map < 0):
allCount = allCount + levelCount
else:
allCount = allCount + levelCount - Map
Map= levelCount
# Return answer
return allCount
# Driver Code
List = [ "abab", "gfg" ]
for s in List:
cnt = countSub(s)
withEmptyString = cnt + 1
print("With empty string count for",
s, "is", withEmptyString)
print("Without empty string count for",
s, "is", cnt)
# This code is contributed by rag2127
C#
// C# Program for above approach
using System;
using System.Collections.Generic;
class GFG{
// Returns count of distinct
// subsequences of str.
public static int countSub(String s)
{
Dictionary<char,
int> map = new Dictionary<char,
int>();
// Iterate from 0 to s.length()
for(int i = 0; i < s.Length; i++)
{
if (!map.ContainsKey(s[i]))
{
map.Add(s[i], -1);
}
}
int allCount = 0;
int levelCount = 0;
// Iterate from 0 to s.length()
for(int i = 0; i < s.Length; i++)
{
char c = s[i];
// Check if i equal to 0
if (i == 0)
{
allCount = 1;
if (!map.ContainsKey(c))
{
map.Add(c, 1);
}
else
{
map = 1;
}
levelCount = 1;
continue;
}
// Replace levelCount with
// allCount + 1
levelCount = allCount + 1;
// If map is less than 0
if (map.ContainsKey(c))
{
if (map < 0)
{
allCount = (allCount + levelCount);
}
else
{
allCount = (allCount +
levelCount - map);
}
}
if (!map.ContainsKey(c))
{
map.Add(c, levelCount);
}
else
{
map = levelCount;
}
}
// Return answer
return allCount;
}
// Driver Code
static void Main()
{
List<string> list = new List<string>();
list.Add("abab");
list.Add("gfg");
foreach(string s in list)
{
int cnt = countSub(s);
int withEmptyString = cnt + 1;
Console.WriteLine("With empty string count for " +
s + " is " + withEmptyString);
Console.WriteLine("Without empty string count for " +
s + " is " + cnt);
}
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript Program for above approach
// Returns count of distinct
// subsequences of str.
function countSub(s)
{
let map = new Map();
// Iterate from 0 to s.length()
for(let i = 0; i < s.length; i++)
{
map.set(s[i], -1);
}
let allCount = 0;
let levelCount = 0;
// Iterate from 0 to s.length()
for(let i=0;i<s.length;i++)
{
let c = s[i];
// Check if i equal to 0
if(i==0)
{
allCount = 1;
map.set(c,1);
levelCount = 1;
continue;
}
// Replace levelCount with
// allCount + 1
levelCount = allCount + 1;
// If map is less than 0
if(map.get(c)<0)
{
allCount = allCount + levelCount;
}
else
{
allCount = allCount + levelCount - map.get(c);
}
map.set(c,levelCount);
}
// Return answer
return allCount;
}
// Driver Code
let list=["abab","gfg"];
for(let i=0;i<list.length;i++)
{
let cnt = countSub(list[i]);
let withEmptyString = cnt+1;
document.write("With empty string count for " +
list[i] +" is " + withEmptyString+"<br>");
document.write("Without empty string count for " +
list[i] + " is " + cnt+"<br>");
}
// This code is contributed by unknown2108
</script>
Producción
With empty string count for abab is 12 Without empty string count for abab is 11 With empty string count for gfg is 7 Without empty string count for gfg is 6
Complejidad de tiempo: O(n)
Complejidad de espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA