- Dada una string, encuentre la longitud de ventana más pequeña con todos los caracteres distintos de la string dada. Por ej. str = “aabcbcdbca”, entonces el resultado sería 4 ya que la ventana más pequeña será “dbca”.
Ejemplos:
Input: aabcbcdbca
Output: dbca
Explanation:
Possible substrings= {aabcbcd, abcbcd,
bcdbca, dbca....}
Of the set of possible substrings 'dbca'
is the shortest substring having all the
distinct characters of given string.
Input: aaab
Output: ab
Explanation:
Possible substrings={aaab, aab, ab}
Of the set of possible substrings 'ab'
is the shortest substring having all
the distinct characters of given string.
Solución: El problema anterior establece que tenemos que encontrar la ventana más pequeña que contenga todos los caracteres distintos de la string dada, incluso si la string más pequeña contiene elementos repetidos.
Por ejemplo, en “aabcbcdb”, la string más pequeña que contiene todos los caracteres es “abcbcd”.
Método 1 : este es el método de fuerza bruta para resolver el problema usando HashMap.
Enfoque: para resolver el problema, primero tenemos que encontrar todos los caracteres distintos presentes en la string. Esto se puede hacer usando un HashMap . Lo siguiente es generar todas las substrings posibles. Esto sigue al verificar si una substring generada tiene todos los caracteres requeridos (almacenados en hash_map) o no. En caso afirmativo, compare su longitud con la longitud mínima de la substring que sigue las restricciones anteriores, encontradas hasta ahora.
Mapa hash :HashMap es parte de la colección de Java desde Java 1.2. Proporciona la implementación básica de la interfaz Map de Java. Almacena los datos en pares (Clave, Valor). Para acceder a un valor se debe conocer su clave. HashMap se conoce como HashMap porque utiliza una técnica llamada Hashing. Hashing es una técnica de convertir una string grande en una string pequeña que representa la misma string. Un valor más corto ayuda en la indexación y búsquedas más rápidas. HashSet también usa HashMap internamente. Utiliza internamente una lista de enlaces para almacenar pares clave-valor ya explicados en detalle en HashSet y otros artículos.
Algoritmo:
- Almacene todos los caracteres distintos de la string dada en un hash_map.
- Tome un conteo variable e inicialícelo con el valor 0.
- Genere las substrings usando dos punteros.
- Ahora verifique si la substring generada es válida o no:
- Tan pronto como descubramos que el carácter de la substring generada no se ha encontrado antes, incremente el conteo en 1 .
- Podemos usar una array visitada de tamaño max_chars para encontrar si el carácter actual se ha encontrado antes o no.
- Si el recuento es igual al tamaño de hash_map, la substring generada es válida
- Si es una substring válida, compárela con la substring de longitud mínima ya generada.
Pseudocódigo:
maphash_map;
for ( i=0 to str.length())
hash_map[str[i]]++;//finding all distinct characters of string
minimum_size=INT_MAX
Distinct_chars=hash_map.size()
for(i=0 to str.length())
count=0;
sub_str="";
visited[256]={0};
for(j=i to n)
sub_str+=str[j]
if(visited[str[j]]==0)
count++
visited[str[j]]=1;
if(count==Distinct_chars)
end loop
if(sub_str.length()<minimum_size&&
count==Distinct_chars)
ans=sub_str;
return ans
Implementación:
CPP
// C++ program to find the smallest
// window containing all characters
// of a pattern.
#include <bits/stdc++.h>
using namespace std;
const int MAX_CHARS = 256;
// Function to find smallest window containing
// all distinct characters
string findSubString(string str)
{
int n = str.length();
// Count all distinct characters.
int dist_count = 0;
unordered_map<int, int> hash_map;
for (int i = 0; i < n; i++) {
hash_map[str[i]]++;
}
dist_count = hash_map.size();
int size = INT_MAX;
string res;
// Now follow the algorithm discussed in below
for (int i = 0; i < n; i++) {
int count = 0;
int visited[256] = { 0 };
string sub_str = "";
for (int j = i; j < n; j++) {
if (visited[str[j]] == 0) {
count++;
visited[str[j]] = 1;
}
sub_str += str[j];
if (count == dist_count)
break;
}
if (sub_str.length() < size && count == dist_count)
{
res = sub_str;
size=res.length();
}
}
return res;
}
// Driver Code
int main()
{
string str = "aabcbcdbca";
cout << "Smallest window containing all distinct"
" characters is: "
<< findSubString(str);
return 0;
}
Java
import java.io.*;
import java.util.*;
// Java program to find the smallest
// window containing all characters
// of a pattern.
class GFG
{
// Function to find smallest window containing
// all distinct characters
public static String findSubString(String str)
{
int n = str.length();
// Count all distinct characters.
int dist_count = 0;
HashMap<Character, Integer> mp = new HashMap<>();
for (int i = 0; i < n; i++)
{
if (mp.containsKey(str.charAt(i)))
{
Integer a = mp.get(str.charAt(i));
mp.put(str.charAt(i),a+1);
}
else
{
mp.put(str.charAt(i), 1);
}
}
dist_count = mp.size();
int size = Integer.MAX_VALUE;
String res = "";
// Now follow the algorithm discussed in below
for (int i = 0; i < n; i++)
{
int count = 0;
int visited[] = new int[256];
for(int j = 0; j < 256; j++)
visited[j] = 0;
String sub_str = "";
for (int j = i; j < n; j++)
{
if (visited[str.charAt(j)] == 0)
{
count++;
visited[str.charAt(j)] = 1;
}
sub_str += str.charAt(j);
if (count == dist_count)
break;
}
if (sub_str.length() < size && count == dist_count)
{
res = sub_str;
size=res.length();
}
}
return res;
}
// Driver code
public static void main (String[] args)
{
String str = "aabcbcdbca";
System.out.println("Smallest window containing all distinct"+
" characters is: "+ findSubString(str)) ;
}
}
// This code is contributed by Manu Pathria
C#
// Include namespace system
using System;
using System.Collections.Generic;
using System.Collections;
// C# program to find the smallest
// window containing all characters
// of a pattern.
public class GFG
{
// Function to find smallest window containing
// all distinct characters
public static String findSubString(String str)
{
var n = str.Length;
// Count all distinct characters.
var dist_count = 0;
var mp = new Dictionary<char, int>();
for (int i = 0; i < n; i++)
{
if (mp.ContainsKey(str[i]))
{
var a = mp[str[i]];
mp[str[i]] = a + 1;
}
else
{
mp[str[i]] = 1;
}
}
dist_count = mp.Count;
var size = int.MaxValue;
var res = "";
// Now follow the algorithm discussed in below
for (int i = 0; i < n; i++)
{
var count = 0;
int[] visited = new int[256];
for (int j = 0; j < 256; j++)
{
visited[j] = 0;
}
var sub_str = "";
for (int j = i; j < n; j++)
{
if (visited[str[j]] == 0)
{
count++;
visited[str[j]] = 1;
}
sub_str += str[j];
if (count == dist_count)
{
break;
}
}
if (sub_str.Length < size && count == dist_count)
{
res = sub_str;
size = res.Length;
}
}
return res;
}
// Driver code
public static void Main(String[] args)
{
var str = "aabcbcdbca";
Console.WriteLine("Smallest window containing all distinct" + " characters is: " + GFG.findSubString(str));
}
}
// This code is contributed by mukulsomukesh.
Python3
# Python3 code for the same approach
import sys
MAX_CHARS = 256
# Function to find smallest window containing
# all distinct characters
def findSubString(str):
n = len(str)
# Count all distinct characters.
dist_count = 0
hash_map = {}
for i in range(n):
if(str[i] in hash_map):
hash_map[str[i]] = hash_map[str[i]] + 1
else:
hash_map[str[i]] = 1
dist_count = len(hash_map)
size = sys.maxsize
res = 0
# Now follow the algorithm discussed in below
for i in range(n):
count = 0
visited= [0]*(MAX_CHARS)
sub_str = ""
for j in range(i,n):
if (visited[ord(str[j])] == 0):
count += 1
visited[ord(str[j])] = 1
sub_str += str[j]
if (count == dist_count):
break
if (len(sub_str) < size and count == dist_count):
res = sub_str
size = len(res)
return res
# Driver Code
str = "aabcbcdbca"
print(f"Smallest window containing all distinct characters is: {findSubString(str)}")
# This code is contributed by shinjanpatra.
Javascript
<script>
// JavaScript program to find the smallest
// window containing all characters
// of a pattern.
const MAX_CHARS = 256;
// Function to find smallest window containing
// all distinct characters
function findSubString(str)
{
let n = str.length;
// Count all distinct characters.
let dist_count = 0;
let hash_map = new Map();
for (let i = 0; i < n; i++) {
if(hash_map.has(str[i])){
hash_map.set(str[i],hash_map.get(str[i])+1);
}
else hash_map.set(str[i],1);
}
dist_count = hash_map.size;
let size = Number.MAX_VALUE;
let res;
// Now follow the algorithm discussed in below
for (let i = 0; i < n; i++) {
let count = 0;
let visited= new Array(MAX_CHARS).fill(0);
let sub_str = "";
for (let j = i; j < n; j++) {
if (visited[str.charCodeAt(j)] == 0) {
count++;
visited[str.charCodeAt(j)] = 1;
}
sub_str += str[j];
if (count == dist_count)
break;
}
if (sub_str.length < size && count == dist_count)
{
res = sub_str;
size = res.length;
}
}
return res;
}
// Driver Code
let str = "aabcbcdbca";
document.write("Smallest window containing all distinct characters is: " + findSubString(str),"</br>");
// This code is contributed by shinjanpatra.
</script>
Producción
Smallest window containing all distinct characters is: dbca
Análisis de Complejidad:
- Complejidad de tiempo: O(N^2).
Este tiempo es necesario para generar todas las substrings posibles de una string de longitud «N». - Complejidad espacial: O(N).
Como se ha utilizado un hash_map de tamaño N.
Método 2 : aquí hemos utilizado la técnica de la ventana deslizante para llegar a la solución. Esta técnica muestra cómo un bucle for anidado en algunos problemas se puede convertir en un bucle for único y, por lo tanto, reduce la complejidad del tiempo.
Enfoque: Básicamente, una ventana de caracteres se mantiene mediante el uso de dos punteros, a saber, inicio y fin . Estos punteros de inicio y final se pueden usar para reducir y aumentar el tamaño de la ventana, respectivamente. Cada vez que la ventana contiene todos los caracteres de la string dada, la ventana se reduce desde el lado izquierdo para eliminar los caracteres adicionales y luego se compara su longitud con la ventana más pequeña encontrada hasta el momento.
Si en la ventana actual, no se pueden eliminar más caracteres, entonces comenzamos a aumentar el tamaño de la ventana usando el final hasta que todos los caracteres distintos presentes en la string también estén allí en la ventana. Finalmente, encuentre el tamaño mínimo de cada ventana.
Algoritmo:
- Mantenga una array (visitada) del máximo de caracteres posibles (256 caracteres) y tan pronto como encontremos alguno en la string, marque ese índice en la array (esto es para contar todos los caracteres distintos en la string).
- Tome dos punteros de inicio y final que marcarán el inicio y el final de la ventana.
- Tome un contador = 0 que se usará para contar distintos caracteres en la ventana.
- Ahora comience a leer los caracteres de la string dada y si encontramos un carácter que aún no ha sido visitado, incremente el contador en 1 .
- Si el contador es igual al número total de caracteres distintos, intente reducir la ventana.
- Para encoger la ventana -:
- Si la frecuencia del carácter en el puntero de inicio es mayor que 1 , incremente el puntero ya que es redundante.
- Ahora compare la longitud de la ventana actual con la longitud mínima de la ventana.
Implementación:
C++
// C++ program to find the smallest
// window containing all characters
// of a pattern.
#include <bits/stdc++.h>
using namespace std;
const int MAX_CHARS = 256;
// Function to find smallest window containing
// all distinct characters
string findSubString(string str)
{
int n = str.length();
// if string is empty or having one char
if (n <= 1)
return str;
// Count all distinct characters.
int dist_count = 0;
bool visited[MAX_CHARS] = { false };
for (int i = 0; i < n; i++) {
if (visited[str[i]] == false) {
visited[str[i]] = true;
dist_count++;
}
}
// Now follow the algorithm discussed in below
// post. We basically maintain a window of characters
// that contains all characters of given string.
int start = 0, start_index = -1, min_len = INT_MAX;
int count = 0;
int curr_count[MAX_CHARS] = { 0 };
for (int j = 0; j < n; j++) {
// Count occurrence of characters of string
curr_count[str[j]]++;
// If any distinct character matched,
// then increment count
if (curr_count[str[j]] == 1)
count++;
// if all the characters are matched
if (count == dist_count) {
// Try to minimize the window i.e., check if
// any character is occurring more no. of times
// than its occurrence in pattern, if yes
// then remove it from starting and also remove
// the useless characters.
while (curr_count[str[start]] > 1) {
if (curr_count[str[start]] > 1)
curr_count[str[start]]--;
start++;
}
// Update window size
int len_window = j - start + 1;
if (min_len > len_window) {
min_len = len_window;
start_index = start;
}
}
}
// Return substring starting from start_index
// and length min_len
return str.substr(start_index, min_len);
}
// Driver code
int main()
{
string str = "aabcbcdbca";
cout << "Smallest window containing all distinct"
" characters is: "
<< findSubString(str);
return 0;
}
Java
// Java program to find the smallest window containing
// all characters of a pattern.
import java.util.Arrays;
public class GFG {
static final int MAX_CHARS = 256;
// Function to find smallest window containing
// all distinct characters
static String findSubString(String str)
{
int n = str.length();
// if string is empty or having one char
if (n <= 1)
return str;
// Count all distinct characters.
int dist_count = 0;
boolean[] visited = new boolean[MAX_CHARS];
Arrays.fill(visited, false);
for (int i = 0; i < n; i++) {
if (visited[str.charAt(i)] == false) {
visited[str.charAt(i)] = true;
dist_count++;
}
}
// Now follow the algorithm discussed in below
// post. We basically maintain a window of
// characters that contains all characters of given
// string.
int start = 0, start_index = -1;
int min_len = Integer.MAX_VALUE;
int count = 0;
int[] curr_count = new int[MAX_CHARS];
for (int j = 0; j < n; j++) {
// Count occurrence of characters of string
curr_count[str.charAt(j)]++;
// If any distinct character matched,
// then increment count
if (curr_count[str.charAt(j)] == 1)
count++;
// if all the characters are matched
if (count == dist_count) {
// Try to minimize the window i.e., check if
// any character is occurring more no. of
// times than its occurrence in pattern, if
// yes then remove it from starting and also
// remove the useless characters.
while (curr_count[str.charAt(start)] > 1) {
if (curr_count[str.charAt(start)] > 1)
curr_count[str.charAt(start)]--;
start++;
}
// Update window size
int len_window = j - start + 1;
if (min_len > len_window) {
min_len = len_window;
start_index = start;
}
}
}
// Return substring starting from start_index
// and length min_len
return str.substring(start_index,
start_index + min_len);
}
// Driver code
public static void main(String args[])
{
String str = "aabcbcdbca";
System.out.println(
"Smallest window containing all distinct"
+ " characters is: " + findSubString(str));
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python program to find the smallest
# window containing
# all characters of a pattern
from collections import defaultdict
MAX_CHARS = 256
# Function to find smallest window
# containing all distinct characters
def findSubString(strr):
n = len(strr)
# if string is empty or having one char
if n <= 1:
return strr
# Count all distinct characters.
dist_count = len(set([x for x in strr]))
curr_count = defaultdict(lambda: 0)
count = 0
start = 0
min_len = n
# Now follow the algorithm discussed in below
# post. We basically maintain a window of characters
# that contains all characters of given string.
for j in range(n):
curr_count[strr[j]] += 1
# If any distinct character matched,
# then increment count
if curr_count[strr[j]] == 1:
count += 1
# Try to minimize the window i.e., check if
# any character is occurring more no. of times
# than its occurrence in pattern, if yes
# then remove it from starting and also remove
# the useless characters.
if count == dist_count:
while curr_count[strr[start]] > 1:
if curr_count[strr[start]] > 1:
curr_count[strr[start]] -= 1
start += 1
# Update window size
len_window = j - start + 1
if min_len > len_window:
min_len = len_window
start_index = start
# Return substring starting from start_index
# and length min_len """
return str(strr[start_index: start_index +
min_len])
# Driver code
if __name__ == '__main__':
print("Smallest window containing "
"all distinct characters is: {}".format(
findSubString("aabcbcdbca")))
# This code is contributed by
# Subhrajit
C#
// C# program to find the smallest window containing
// all characters of a pattern.
using System;
class GFG {
static int MAX_CHARS = 256;
// Function to find smallest window containing
// all distinct characters
static string findSubString(string str)
{
int n = str.Length;
// if string is empty or having one char
if (n <= 1)
return str;
// Count all distinct characters.
int dist_count = 0;
bool[] visited = new bool[MAX_CHARS];
for (int i = 0; i < n; i++) {
if (visited[str[i]] == false) {
visited[str[i]] = true;
dist_count++;
}
}
// Now follow the algorithm discussed in below
// post. We basically maintain a window of
// characters that contains all characters of given
// string.
int start = 0, start_index = -1,
min_len = int.MaxValue;
int count = 0;
int[] curr_count = new int[MAX_CHARS];
for (int j = 0; j < n; j++) {
// Count occurrence of characters of string
curr_count[str[j]]++;
// If any distinct character matched,
// then increment count
if (curr_count[str[j]] == 1)
count++;
// if all the characters are matched
if (count == dist_count) {
// Try to minimize the window i.e., check if
// any character is occurring more no. of
// times than its occurrence in pattern, if
// yes then remove it from starting and also
// remove the useless characters.
while (curr_count[str[start]] > 1) {
if (curr_count[str[start]] > 1)
curr_count[str[start]]--;
start++;
}
// Update window size
int len_window = j - start + 1;
if (min_len > len_window) {
min_len = len_window;
start_index = start;
}
}
}
// Return substring starting from start_index
// and length min_len
return str.Substring(start_index, min_len);
}
// Driver code
public static void Main(String[] args)
{
string str = "aabcbcdbca";
Console.WriteLine(
"Smallest window containing all distinct"
+ " characters is: " + findSubString(str));
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to find the smallest
// window containing all characters
// of a pattern.
const MAX_CHARS = 256;
// Function to find smallest window containing
// all distinct characters
function findSubString(str)
{
let n = str.length;
// if string is empty or having one char
if (n <= 1)
return str;
// Count all distinct characters.
let dist_count = 0;
let visited = new Array(MAX_CHARS).fill(false);
for (let i = 0; i < n; i++) {
if (visited[str.charCodeAt(i)] == false) {
visited[str.charCodeAt(i)] = true;
dist_count++;
}
}
// Now follow the algorithm discussed in below
// post. We basically maintain a window of characters
// that contains all characters of given string.
let start = 0, start_index = -1, min_len = Number.MAX_VALUE;
let count = 0;
let curr_count = new Array(MAX_CHARS).fill(0);
for (let j = 0; j < n; j++) {
// Count occurrence of characters of string
curr_count[str.charCodeAt(j)]++;
// If any distinct character matched,
// then increment count
if (curr_count[str.charCodeAt(j)] == 1)
count++;
// if all the characters are matched
if (count == dist_count) {
// Try to minimize the window i.e., check if
// any character is occurring more no. of times
// than its occurrence in pattern, if yes
// then remove it from starting and also remove
// the useless characters.
while (curr_count[str.charCodeAt(start)] > 1) {
if (curr_count[str.charCodeAt(start)] > 1)
curr_count[str.charCodeAt(start)]--;
start++;
}
// Update window size
let len_window = j - start + 1;
if (min_len > len_window) {
min_len = len_window;
start_index = start;
}
}
}
// Return substring starting from start_index
// and length min_len
return str.substring(start_index, min_len + start_index);
}
// Driver code
let str = "aabcbcdbca";
document.write("Smallest window containing all distinct characters is: " +
findSubString(str),"</br>");
// This code is contributed by shinjanpatra.
</script>
Producción
Smallest window containing all distinct characters is: dbca
Análisis de Complejidad:
- Complejidad temporal: O(N).
A medida que la string se recorre usando dos punteros solo una vez. - Complejidad espacial: O(N).
Como se usa un hash_map de tamaño N
Artículo relacionado:
- Longitud de la substring más pequeña que consta de un máximo de caracteres distintos
- https://www.geeksforgeeks.org/find-the-smallest-window-in-a-string-containing-all-characters-of-another-string/
Este artículo es una contribución de Sahil Chhabra . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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