Dadas dos strings A y B , la tarea es encontrar la substring más pequeña de A que tenga B como subsecuencia .
Ejemplos:
Entrada: A = «abcdefababaef», B = «abf»
Salida: 5
Explicación:
la substring más pequeña de A que tiene B como subsecuencia es abcdef.
Por lo tanto, la longitud requerida es 5.Entrada: A = “abcdefababaef”, B = “aef”
Salida: 3
Enfoque: siga los pasos a continuación para resolver el problema:
- Almacene todos los índices de los caracteres de A que también están presentes en B en un Map CharacterIndex .
- Recorra todos los caracteres de la string B .
- Compruebe si el primer carácter de la string B está presente en la string A o no:
- Si se determina que es cierto, inicialice dos variables firstVar y lastVar con el índice de la primera aparición de B[0] en la string A .
- Después de actualizar los valores, elimine ese carácter del Map CharacterIndex .
- De lo contrario, no es posible ninguna substring adicional.
- Para los caracteres restantes de B , verifique si el carácter está presente en la string A o no. Si se determina que es cierto, recorra todas las apariciones de ese carácter en la string A y si el índice de ese carácter en la string A excede lastVar , actualice lastVar con ese índice. De lo contrario, no es posible ninguna substring adicional.
- Si B se recorre por completo, actualice la respuesta con la diferencia entre firstVar y lastVar.
- Imprime la respuesta final minimizada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the length of
// smallest substring of a having
// string b as a subsequence
int minLength(string a, string b)
{
// Stores the characters present
// in string b
map<char, int> Char;
for (int i = 0; i < b.length(); i++) {
Char[b[i]]++;
}
// Find index of characters of a
// that are also present in string b
map<char, vector<int> > CharacterIndex;
for (int i = 0; i < a.length(); i++) {
char x = a[i];
// If character is present in string b
if (Char.find(x) != Char.end()) {
// Store the index of character
CharacterIndex[x].push_back(i);
}
}
int len = INT_MAX;
// Flag is used to check if
// substring is possible
int flag;
while (true) {
// Assume that substring is
// possible
flag = 1;
// Stores first and last
// indices of the substring
// respectively
int firstVar, lastVar;
for (int i = 0; i < b.length(); i++) {
// For first character of string b
if (i == 0) {
// If the first character of
// b is not present in a
if (CharacterIndex.find(b[i])
== CharacterIndex.end()) {
flag = 0;
break;
}
// If the first character of b
// is present in a
else {
int x = *(
CharacterIndex[b[i]].begin());
// Remove the index from map
CharacterIndex[b[i]].erase(
CharacterIndex[b[i]].begin());
// Update indices of
// the substring
firstVar = x;
lastVar = x;
}
}
// For the remaining characters of b
else {
int elementFound = 0;
for (auto e : CharacterIndex[b[i]]) {
if (e > lastVar) {
// If index possible for
// current character
elementFound = 1;
lastVar = e;
break;
}
}
if (elementFound == 0) {
// If no index is possible
flag = 0;
break;
}
}
}
if (flag == 0) {
// If no more substring
// is possible
break;
}
// Update the minimum length
// of substring
len = min(len,
abs(lastVar - firstVar) + 1);
}
// Return the result
return len;
}
// Driver Code
int main()
{
// Given two string
string a = "abcdefababaef";
string b = "abf";
int len = minLength(a, b);
if (len != INT_MAX) {
cout << len << endl;
}
else {
cout << "Impossible" << endl;
}
}
Java
// Java program to implement
// the above approach
import java.util.ArrayList;
import java.util.HashMap;
class GFG{
// Function to find the length of
// smallest substring of a having
// string b as a subsequence
static int minLength(String a, String b)
{
// Stores the characters present
// in string b
HashMap<Character, Integer> Char = new HashMap<>();
for(int i = 0; i < b.length(); i++)
{
Char.put(b.charAt(i),
Char.getOrDefault(b.charAt(i), 0) + 1);
}
// Find index of characters of a
// that are also present in string b
HashMap<Character, ArrayList<Integer>>
CharacterIndex = new HashMap<>();
for(int i = 0; i < a.length(); i++)
{
char x = a.charAt(i);
// If character is present in string b
if (Char.containsKey(x))
{
if (CharacterIndex.get(x) == null)
{
CharacterIndex.put(
x, new ArrayList<Integer>());
}
// Store the index of character
CharacterIndex.get(x).add(i);
}
}
int len = Integer.MAX_VALUE;
// Flag is used to check if
// substring is possible
int flag;
while (true)
{
// Assume that substring is
// possible
flag = 1;
// Stores first and last
// indices of the substring
// respectively
int firstVar = 0, lastVar = 0;
for(int i = 0; i < b.length(); i++)
{
// For first character of string b
if (i == 0)
{
// If the first character of
// b is not present in a
if (CharacterIndex.containsKey(i))
{
flag = 0;
break;
}
// If the first character of b
// is present in a
else
{
int x = CharacterIndex.get(b.charAt(i)).get(0);
// Remove the index from map
CharacterIndex.get(b.charAt(i)).remove(
CharacterIndex.get(b.charAt(i)).get(0));
// Update indices of
// the substring
firstVar = x;
lastVar = x;
}
}
// For the remaining characters of b
else
{
int elementFound = 0;
for(var e :
CharacterIndex.get(b.charAt(i)))
{
if (e > lastVar)
{
// If index possible for
// current character
elementFound = 1;
lastVar = e;
break;
}
}
if (elementFound == 0)
{
// If no index is possible
flag = 0;
break;
}
}
}
if (flag == 0)
{
// If no more substring
// is possible
break;
}
// Update the minimum length
// of substring
len = Math.min(
len, Math.abs(lastVar - firstVar) + 1);
}
// Return the result
return len;
}
// Driver code
public static void main(String[] args)
{
// Given two string
String a = "abcdefababaef";
String b = "abf";
int len = minLength(a, b);
if (len != Integer.MAX_VALUE)
{
System.out.println(len);
}
else
{
System.out.println("Impossible");
}
}
}
// This code is contributed by sk944795
Python3
# Python3 program to implement
# the above approach
import sys
# Function to find the length of
# smallest substring of a having
# string b as a subsequence
def minLength(a, b):
# Stores the characters present
# in string b
Char = {}
for i in range(len(b)):
Char[b[i]] = Char.get(b[i], 0) + 1
# Find index of characters of a
# that are also present in string b
CharacterIndex = {}
for i in range(len(a)):
x = a[i]
# If character is present in string b
if (x in Char):
# Store the index of character
CharacterIndex[x] = CharacterIndex.get(x, [])
CharacterIndex[x].append(i)
l = sys.maxsize
# Flag is used to check if
# substring is possible
while(True):
# Assume that substring is
# possible
flag = 1
firstVar = 0
lastVar = 0
# Stores first and last
# indices of the substring
# respectively
for i in range(len(b)):
# For first character of string b
if (i == 0):
# If the first character of
# b is not present in a
if (b[i] not in CharacterIndex):
flag = 0
break
# If the first character of b
# is present in a
else:
x = CharacterIndex[b[i]][0]
# Remove the index from map
CharacterIndex[b[i]].remove(
CharacterIndex[b[i]][0])
# Update indices of
# the substring
firstVar = x
lastVar = x
# For the remaining characters of b
else:
elementFound = 0
for e in CharacterIndex[b[i]]:
if (e > lastVar):
# If index possible for
# current character
elementFound = 1
lastVar = e
break
if (elementFound == 0):
# If no index is possible
flag = 0
break
if (flag == 0):
# If no more substring
# is possible
break
# Update the minimum length
# of substring
l = min(l, abs(lastVar - firstVar) + 1)
# Return the result
return l
# Driver Code
if __name__ == '__main__':
# Given two string
a = "abcdefababaef"
b = "abf"
l = minLength(a, b)
if (l != sys.maxsize):
print(l)
else:
print("Impossible")
# This code is contributed by SURENDRA_GANGWAR
Producción:
5
Complejidad Temporal: O(N 2 )
Espacio Auxiliar: O(N), ya que se ha tomado N espacio extra.