Tous les défis
Difficile 1 résolu 50.0 % de réussite

Minimum Window Substring

Find the shortest piece of text containing all required characters.

Ce que vous allez apprendre

  • Agrandir et réduire une fenêtre sur un texte
  • Suivre le nombre de caractères requis
  • Trouver la plus courte fenêtre valide

Problème

Find the shortest contiguous substring of text that contains every character of pattern, including repeats. If several are equally short, return the leftmost.

Implement min_window(text, pattern).

Input

text: The text to search. pattern: The characters that must appear.

Output

Return the shortest window, or an empty string if none exists.

Contraintes

1 ≤ length of text, pattern ≤ 100,000 (ASCII)

Exemples

Exemple 1
Entrée :
text = "ADOBECODEBANC"
pattern = "ABC"

Sortie attendue :
expected = "BANC"
Entrée :
std::string text = "ADOBECODEBANC";
std::string pattern = "ABC";

Sortie attendue :
std::string expected = "BANC";
Entrée :
string text = "ADOBECODEBANC";
string pattern = "ABC";

Sortie attendue :
string expected = "BANC";

Explication

"BANC" contains A, B and C and nothing shorter does.

Exemple 2
Entrée :
text = "a"
pattern = "aa"

Sortie attendue :
expected = ""
Entrée :
std::string text = "a";
std::string pattern = "aa";

Sortie attendue :
std::string expected = "";
Entrée :
string text = "a";
string pattern = "aa";

Sortie attendue :
string expected = "";

Explication

Two a's are needed but the text has only one: "".

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

La fenêtre doit couvrir tous les comptes de caractères nécessaires, pas seulement les caractères distincts.

Indice 2

Étends jusqu’à être valide, puis rétrécis par la gauche pour retirer les caractères inutiles tout en restant valide.

Indice 3

Si plusieurs fenêtres ont la même longueur minimale, garde la plus ancienne quand tu mets à jour la meilleure réponse.

Complexité attendue

temps O(n), espace supplémentaire O(1)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 835 ms - 5/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 1 solution complète ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.