Dadas dos strings str1 y str2 de longitudes N y M respectivamente, la tarea es verificar si str2 se puede formar agregando subsecuencias de str1 varias veces. Si es posible, imprima el número mínimo de operaciones de adición requeridas. De lo contrario, imprima -1 .
Ejemplos:
Entrada: str1 = “abb”, str2 = “ababbbbb”
Salida: 4
Explicación:
La string str2 se puede formar agregando subsecuencias de str1 = “ab” + “abb” + “bb” + “b” = “ababbbbb”. Dado que se requieren al menos 4 operaciones, imprima 4.Entrada: str1 = “mt”, str2 = “atttm”
Salida: -1
Explicación:
Dado que ‘a’ no está presente en la string str1, str2 no se puede generar a partir de str1. Por lo tanto, imprima -1.
Enfoque: La idea es utilizar el concepto de Hashing basado en las siguientes observaciones a continuación:
- Considere las strings str1 = “abb” y str2 = “aba” . Encuentre la posición del carácter str2[0] en str1 cuyo índice sea mayor o igual a 0 , es decir, el índice 0 de str1 .
- Nuevamente, encuentre str2[1] en str1 tal que su índice sea mayor o igual a 1 , es decir, el índice 1 de str1 .
- Luego, encuentre str2[2] en str1 tal que su índice sea mayor o igual a 2 que no existe.
- Por lo tanto, comience de nuevo desde el índice 0 y busque str2[2] en str1 que tenga un índice mayor o igual que el índice 0 , es decir, el índice 0 de str1 .
- Por lo tanto, se pueden agregar dos subsecuencias «ab» y «a» para formar «aba» .
Siga los pasos a continuación para resolver el problema:
- Inicialice una array de vectores vec[] de longitud 26 .
- Empuje todos los índices str1 que tengan el carácter ‘a’ en vec[0] . Del mismo modo, inserte todos los índices que tengan el carácter ‘b’ en vec[1] . Haga esto para cada carácter de ‘a’ a ‘z’ .
- Inicialice una variable result con 1 y position con 0 para almacenar las operaciones mínimas y la posición actual de str1 .
- Recorra la string str2 sobre el rango [0, M] y para cada carácter haga lo siguiente:
- Si vec[str2[i] – ‘a’] está vacío, entonces el carácter str2[i] no está presente en str1 . Por lo tanto, la respuesta no es posible. Por lo tanto, imprima -1 .
- De lo contrario, busque el límite inferior de la posición en vec[str2[i] – ‘a’] . Que sea p . Si p es igual al tamaño de vec[str2[i] – ‘a’] entonces incremente el resultado en 1 y disminuya i en 1 ya que la respuesta para el carácter str2[i] aún no se encuentra y establezca la posición en 0 .
- De lo contrario, establezca la posición como (vec[p] + 1) .
- Después de atravesar, imprima el resultado como las operaciones mínimas requeridas.
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 find minimum operations
// required to form str2 by adding
// subsequences of str1
void find(string str1, string str2)
{
// Initialize vector of length 26
vector<int> vec1[26];
// Push indices of characters of str1
for (int i = 0; i < str1.size(); i++)
vec1[str1[i] - 'a'].push_back(i);
// Initialize the result & position
int result = 1, position = 0;
// Traverse the string str2
for (int i = 0; i < str2.size(); i++)
{
char c = str2[i];
// Return if no answer exist
if (vec1.empty())
{
result = -1;
break;
}
// Pointer of vec1[c-'a']
vector<int>& vec2 = vec1;
// Lower bound of position
int p = lower_bound(vec2.begin(),
vec2.end(),
position)
- vec2.begin();
// If no index found
if (p == vec2.size())
{
// Increment result
result++;
i--;
position = 0;
continue;
}
// Update the position
else {
position = vec2[p] + 1;
}
}
// Print the result
cout << result << '\n';
}
// Driver Code
int main()
{
// Given string str1 & str2
string str1 = "abb", str2 = "ababbbbb";
// Function Call
find(str1, str2);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
static void find(String str1, String str2)
{
List<List<Integer> > vec1
= new ArrayList<List<Integer> >();
// Initialize vector of length 26
for (int i = 0; i < 26; i++) {
vec1.add(new ArrayList<Integer>());
}
// Push indices of characters of str1
for (int i = 0; i < str1.length(); i++)
vec1.get(str1.charAt(i) - 'a').add(i);
// Initialize the result & position
int result = 1, position = 0;
// Traverse the string str2
for (int i = 0; i < str2.length(); i++)
{
char c = str2.charAt(i);
// Return if no answer exist
if (vec1.get(c - 'a').size() == 0)
{
result = -1;
break;
}
List<Integer> vec2 = vec1.get(c - 'a');
// Lower bound of position
int p = lower_bound(vec2, position);
// If no index found
if (p == vec2.size())
{
// Increment result
result++;
i--;
position = 0;
continue;
}
// Update the position
else {
position = vec2.get(p) + 1;
}
}
// Print the result
System.out.println(result);
}
// Driver Code
static int lower_bound(List<Integer> vec2, int position)
{
int low = 0, high = vec2.size() - 1;
while (low < high) {
int mid = (low + high) / 2;
if (vec2.get(mid) < position)
low = mid + 1;
else
high = mid;
}
return (vec2.get(low) < position) ? low + 1 : low;
}
public static void main(String[] args)
{
// Given string str1 & str2
String str1 = "abb", str2 = "ababbbbb";
// Function Call
find(str1, str2);
}
}
Python3
# Python3 program for the above approach
from bisect import bisect_left
# Function to find minimum operations
# required to form str2 by adding
# subsequences of str1
def find(str1, str2):
# Initialize vector of length 26
vec1 = [[] for i in range(26)]
# Push indices of characters of str1
for i in range(len(str1)):
vec1[ord(str1[i]) - ord('a')].append(i)
# Initialize the result & position
result = 1
position = 0
# Traverse the str2
i = 0
while i < len(str2):
c = str2[i]
# Return if no answer exist
if (len(vec1[ord(c) - ord('a')]) == 0):
result = -1
break
# Pointer of vec1[c-'a']
vec2 = vec1[ord(c) - ord('a')]
# Lower bound of position
p = bisect_left(vec2, position)
#print(c)
# If no index found
if (p == len(vec2)):
# Increment result
result += 1
#i-=1
position = 0
continue
# Update the position
else:
i += 1
position = vec2[p] + 1
# Print the result
print(result)
# Driver Code
if __name__ == '__main__':
# Given str1 & str2
str1 = "abb"
str2 = "ababbbbb"
# Function Call
find(str1, str2)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find minimum operations
// required to form str2 by adding
// subsequences of str1
static void find(string str1, string str2)
{
List<List<int>> vec1 = new List<List<int>>();
// Initialize vector of length 26
for(int i = 0; i < 26; i++)
{
vec1.Add(new List<int>());
}
// Push indices of characters of str1
for(int i = 0; i < str1.Length; i++)
{
vec1[str1[i] - 'a'].Add(i);
}
// Initialize the result & position
int result = 1, position = 0;
// Traverse the string str2
for(int i = 0; i < str2.Length; i++)
{
char c = str2[i];
// Return if no answer exist
if (vec1.Count == 0)
{
result = -1;
break;
}
List<int> vec2 = vec1;
// Lower bound of position
int p = lower_bound(vec2, position);
// If no index found
if (p == vec2.Count)
{
// Increment result
result++;
i--;
position = 0;
continue;
}
// Update the position
else
{
position = vec2[p] + 1;
}
}
// Print the result
Console.WriteLine(result);
}
static int lower_bound(List<int> vec2,
int position)
{
int low = 0, high = vec2.Count - 1;
while (low < high)
{
int mid = (low + high) / 2;
if (vec2[mid] < position)
{
low = mid + 1;
}
else
{
high = mid;
}
}
return (vec2[low] < position) ?
low + 1 : low;
}
// Driver Code
static public void Main()
{
// Given string str1 & str2
string str1 = "abb", str2 = "ababbbbb";
// Function Call
find(str1, str2);
}
}
// This code is contributed by avanitrachhadiya2155
Producción
4
Complejidad de Tiempo: O(N + M log N)
Espacio Auxiliar: O(M + N)
Publicación traducida automáticamente
Artículo escrito por topdogbaker1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA