Dada una array arr[] de N strings y Q consultas donde cada una de las consultas contiene algunos caracteres, la tarea es verificar si para cada consulta las subsecuencias de todas las strings solo están compuestas por todas las ocurrencias de los caracteres de esa consulta son iguales o no.
Una subsecuencia es una secuencia que se puede derivar de la secuencia dada eliminando algunos o ningún elemento sin cambiar el orden de los elementos restantes.
Ejemplos:
Entrada: arr[] = {“accbad”, “abcacd”, “cacbda”}, consultas[] = {{‘a’}, {‘a’, ‘b’}, {‘a’, ‘d’} , {‘b’, ‘c’, ‘d’}, {‘a’, ‘b’, ‘d’} Salida:
Verdadero
Verdadero
Falso
Verdadero
Falso
Falso
Explicación
: Todas las strings generan la subsecuencia «aa» usando solo el carácter ‘a’.
Todas las strings generan la subsecuencia «aba» usando solo los caracteres ‘a’ y ‘b’.
arr[1] y arr[2] generan la subsecuencia “aad”, pero arr[3] genera la subsecuencia “ada” usando solo los caracteres ‘a’ y ‘d’, y dado que las subsecuencias no coinciden, se imprime falso.
Todas las strings generan la subsecuencia «bd» usando solo los caracteres ‘b’ y ‘d’
arr[1] y arr[3] generan la subsecuencia «ccbd», pero arr[2] genera la subsecuencia «bccd» usando solo los caracteres ‘b’, ‘c’ y ‘d’, por lo que imprime ‘False’.
arr[1] y arr[2] generan la subsecuencia «abad», pero arr[3] genera la subsecuencia «abda» usando solo los caracteres ‘a’, ‘b’ y ‘d’Entrada: arr[] = {“adacb”, “aacbd”}, consultas[] = {{‘a’, ‘b’, ‘c’}} Salida:
Verdadero .
Explicación: Las subsecuencias son ‘aacb’ para ambas strings
Enfoque ingenuo: para cada consulta, genere las subsecuencias que contienen todas las ocurrencias de todos los caracteres de esa consulta y verifique si son iguales o no.
Complejidad temporal: O(Q * N * M), donde M es la longitud media de cada string.
Espacio Auxiliar: O(1)
Enfoque eficiente utilizando la memorización: este problema se puede resolver de manera eficiente en función de la siguiente idea:
Si las posiciones relativas de todos los caracteres de una consulta son las mismas en todas las strings, la subsecuencia es común en todas ellas.
Las posiciones relativas de cualquier carácter (por ejemplo, el carácter ch ), se pueden averiguar encontrando las frecuencias de todos los caracteres de una consulta hasta el índice de ch . Si son iguales, entonces su posición relativa también es la misma.
Siga los pasos mencionados a continuación para implementar la idea:
- Cree una array tridimensional (por ejemplo, elementos [] ) para almacenar la frecuencia de cada carácter de las strings hasta cada índice.
- Atraviesa todas las cuerdas y encuentra la frecuencia y guárdalas
- Ahora verifique las posiciones relativas de los caracteres de una consulta.
- Para implementar esto de manera eficiente, itere a través de la array de strings, compare las strings adyacentes y haga lo siguiente:
- Encuentre la posición relativa de cada carácter con respecto a todos los demás caracteres del alfabeto inglés (la posición relativa se comprueba comprobando las frecuencias de todos los demás caracteres hasta ese índice).
- Si no son los mismos para un carácter (por ejemplo, ch ) en dos strings, agregue los caracteres que causan la falta de coincidencia en un conjunto . (la discrepancia significa que los conteos de frecuencia no son los mismos)
- Compruebe si las discrepancias encontradas son las mismas que los caracteres de la consulta.
- Si es así, las subsecuencias formadas no son las mismas. Así que devuelve falso .
- Una vez que finaliza la iteración y no se devuelve un «falso», las subsecuencias formadas son las mismas.
Siga la ilustración a continuación para una mejor comprensión.
Ilustración:
Diga arr[] = {“adacb”, “aacbd”}, consultas[] = {{‘a’, ‘b’, ‘c’}}
Las frecuencias de todos los caracteres para arr[0] y arr[1] se muestran a continuación
arr[0] =
‘a’
‘d’ ‘a’ ‘C’ ‘b’ a 1 1 2 2 2 b 0 0 0 0 1 C 0 0 0 1 1 d 0 1 1 1 1 array[1] =
‘a’
‘a’ ‘C’ ‘b’ ‘d’ a 1 2 2 2 2 b 0 0 0 1 1 C 0 0 1 1 1 d 0 0 0 0 1 Para ‘a’:
=> Las posiciones relativas de la segunda ‘a’ no son las mismas.
=> En la primera string hay una ‘d’ adicional antes de la segunda ‘a’.
=> Entonces el conjunto de desajustes es { ‘d’ } .Para ‘b’:
=> Las posiciones relativas de ‘b’ no son las mismas.
=> En la primera string hay una ‘d’ adicional antes.
=> Entonces el conjunto de desajustes es { ‘d’ } .Para ‘c’:
=> Las posiciones relativas de ‘c’ no son las mismas.
=> En la primera string hay una ‘d’ adicional antes.
=> Entonces el conjunto de desajustes es { ‘d’ } .Ahora ningún conjunto de discrepancias contiene el mismo carácter que los presentes en la consulta. Entonces la subsecuencia formada es la misma para las strings.
A continuación se muestra la implementación del enfoque anterior.
Java
// Java code to implement the approach
import java.io.*;
import java.util.*;
public class SubsequenceQueries {
// Function to check if
// the subsequences formed are the same
public static ArrayList<Boolean>
isPossible(int N, ArrayList<String> arr, int Q,
String queries[])
{
// For 26 letters
final int numElements = 26;
// Generate prefix sums (for each letter)
// for each string
ArrayList<int[][]> elements
= new ArrayList<>();
for (int i = 0; i < N; i++) {
// Create a new prefix sum array
// and add it to the array list
elements.add(new int[arr.get(i).length()]
[numElements]);
int[][] tmp = elements.get(i);
// Build the prefix sum
// at each position in the string
for (int j = 0; j < arr.get(i).length();
j++) {
for (int k = 0; k < numElements;
k++) {
if (j != 0)
tmp[j][k] = tmp[j - 1][k];
}
// ASCII to int conversion
// for lowercase letters
tmp[j][arr.get(i).charAt(j) - 97]++;
}
}
// Generate the set of characters
// which are necessary to remove.
// Each mapping is the set
// corresponding of characters
// which need to be removed.
// for each letter in order for a
// subsequence to be generated.
HashMap<Integer, Set<Integer> > requiredRemovals
= new HashMap<>();
for (int i = 0; i < numElements; i++)
requiredRemovals.put(i, new HashSet<Integer>());
// Iterate over all the characters
// (in the alphabet in this case)
for (int i = 0; i < numElements; i++) {
// For each character,
// go through all M strings
// to generate prefix sums
for (int j = 1; j < N; j++) {
// String a stores
// the previous string (j-1)
// string b stores
// the current string (j)
String a = arr.get(j - 1);
String b = arr.get(j);
// Store the prefix sums
// for strings a and b
int[][] elements1
= elements.get(j - 1);
int[][] elements2
= elements.get(j);
int p1 = 0;
int p2 = 0;
// Check if the lengths of characters
// differ; if they do, then
// no valid subsequence
// with that character can be generated.
// So for all other letters,
// add that character to its Set.
// Otherwise, check the count
// of each character
// at every position where
// letter i appears in both strings
if (elements1[a.length() - 1][i]
!= elements2[b.length() - 1][i]) {
for (int key :
requiredRemovals.keySet())
requiredRemovals.get(key).add(i);
}
else {
// Iterate through both strings
// using p1 for all characters
// in the first string
// and p2 for all characters
// in the second string
while (p1 < a.length()
&& p2 < b.length()) {
// Skip to the next occurrence of
// character i in string a
while (p1 < a.length()
&& a.charAt(p1)
- 97
!= i) {
p1++;
}
// Skip to the next occurrence of
// character i in string b
while (p2 < b.length()
&& b.charAt(p2)
- 97
!= i) {
p2++;
}
// Compare the count of each
// character to check if they match
// in both strings
if (p1 < a.length()
&& p2 < b.length()) {
// Iterate over
// their prefix sums
for (int k = 0;
k < numElements;
k++) {
if (elements1[p1][k]
!= elements2[p2][k])
requiredRemovals.get(i)
.add(k);
}
}
p1++;
p2++;
}
}
}
}
ArrayList<Boolean> res
= new ArrayList<Boolean>();
// Read in Q queries
for (int i = 0; i < Q; i++) {
// st = new StringTokenizer(br.readLine());
// String q = st.nextToken();
Set<Integer> union
= new HashSet<Integer>();
// generate a combined set of all characters
// which must be removed for a valid subsequence
// to be created with the query string
for (char c : queries[i].toCharArray())
union.addAll(requiredRemovals.get(c - 97));
boolean ans = true;
// if there are any contradictions in the query,
// then the answer will be false
for (char c : queries[i].toCharArray()) {
if (union.contains(c - 97))
ans = false;
}
res.add(ans);
}
return res;
}
// Driver code
public static void main(String[] args)
throws IOException
{
int N = 3;
ArrayList<String> arr
= new ArrayList<String>();
arr.add("accbad");
arr.add("abcacd");
arr.add("cacbda");
int Q = 6;
String queries[]
= new String[6];
queries[0] = "a";
queries[1] = "ab";
queries[2] = "ad";
queries[3] = "bd";
queries[4] = "bcd";
queries[5] = "abd";
// Function call
ArrayList<Boolean> ans
= isPossible(N, arr, Q, queries);
for (boolean val : ans)
System.out.println(val);
}
}
C#
// C# program to implement above approach
using System;
using System.Collections.Generic;
class GFG
{
// For 26 letters
readonly public static int numElements = 26;
// Function to check if
// the subsequences formed are the same
public static List<bool> isPossible(int N, List<String> arr, int Q, String[] queries)
{
// Generate prefix sums (for each letter)
// for each string
List<int[, ]> elements = new List<int[, ]>();
for (int i = 0 ; i < N ; i++) {
// Create a new prefix sum array
// and add it to the array list
elements.Add(new int[arr[i].Length, numElements]);
// Build the prefix sum
// at each position in the string
for (int j = 0 ; j < arr[i].Length ; j++) {
for (int k = 0 ; k < numElements ; k++) {
if(j!=0){
elements[i][j, k] = elements[i][j - 1, k];
}
}
// ASCII to int conversion
// for lowercase letters
elements[i][j, ((int)arr[i][j] - 97)]++;
}
}
// Generate the set of characters
// which are necessary to remove.
// Each mapping is the set
// corresponding of characters
// which need to be removed.
// for each letter in order for a
// subsequence to be generated.
SortedDictionary<int, SortedSet<int>> requiredRemovals = new SortedDictionary<int, SortedSet<int>>();
for (int i = 0 ; i < numElements ; i++){
requiredRemovals.Add(i, new SortedSet<int>());
}
// Iterate over all the characters
// (in the alphabet in this case)
for (int i = 0 ; i < numElements ; i++) {
// For each character,
// go through all M strings
// to generate prefix sums
for (int j = 1 ; j < N ; j++) {
// String a stores
// the previous string (j-1)
// string b stores
// the current string (j)
String a = arr[j - 1];
String b = arr[j];
// Store the prefix sums
// for strings a and b
int[, ] elements1 = elements[j - 1];
int[, ] elements2 = elements[j];
int p1 = 0;
int p2 = 0;
// Check if the lengths of characters
// differ; if they do, then
// no valid subsequence
// with that character can be generated.
// So for all other letters,
// add that character to its Set.
// Otherwise, check the count
// of each character
// at every position where
// letter i appears in both strings
if (elements1[a.Length - 1, i] != elements2[b.Length - 1, i]) {
foreach( KeyValuePair<int, SortedSet<int>> pr in requiredRemovals){
requiredRemovals[pr.Key].Add(i);
}
}
else {
// Iterate through both strings
// using p1 for all characters
// in the first string
// and p2 for all characters
// in the second string
while (p1 < a.Length && p2 < b.Length) {
// Skip to the next occurrence of
// character i in string a
while (p1 < a.Length && ((int)a[p1] - 97) != i) {
p1++;
}
// Skip to the next occurrence of
// character i in string b
while (p2 < b.Length && ((int)b[p2] - 97) != i) {
p2++;
}
// Compare the count of each
// character to check if they match
// in both strings
if (p1 < a.Length && p2 < b.Length) {
// Iterate over
// their prefix sums
for (int k = 0 ; k < numElements; k++) {
if (elements1[p1, k] != elements2[p2, k]){
requiredRemovals[i].Add(k);
}
}
}
p1++;
p2++;
}
}
}
}
List<bool> res = new List<bool>();
// Read in Q queries
for (int i = 0; i < Q; i++) {
// st = new StringTokenizer(br.readLine());
// String q = st.nextToken();
SortedSet<int> union = new SortedSet<int>();
// generate a combined set of all characters
// which must be removed for a valid subsequence
// to be created with the query string
foreach (char c in queries[i].ToCharArray()){
foreach(int x in requiredRemovals[((int)c - 97)]){
union.Add(x);
}
}
bool ans = true;
// if there are any contradictions in the query,
// then the answer will be false
foreach (char c in queries[i].ToCharArray()) {
if (union.Contains((int)c - 97)){
ans = false;
}
}
res.Add(ans);
}
return res;
}
// Driver Code
public static void Main(string[] args){
int N = 3;
List<String> arr = new List<String>();
arr.Add("accbad");
arr.Add("abcacd");
arr.Add("cacbda");
int Q = 6;
String[] queries = new String[6];
queries[0] = "a";
queries[1] = "ab";
queries[2] = "ad";
queries[3] = "bd";
queries[4] = "bcd";
queries[5] = "abd";
// Function call
List<bool> ans = isPossible(N, arr, Q, queries);
foreach(bool val in ans){
Console.Write(val + "\n");
}
}
}
// This code is contributed by subhamgoyal2014.
true true false true false false
Complejidad de Tiempo: O(C 2 * N + Q * N)
Espacio Auxiliar: O(C 2 * N) donde C = 26