Minimum Window Substring

Q: Que compte le compteur manquant ?

C’est le nombre de copies de caractères que t demande et que la fenêtre ne contient pas encore, soit la somme des valeurs positives dans need . Il commence à la longueur de t et vaut 0 exactement lorsque la fenêtre couvre t . Les copies excédentaires ne le modifient jamais, ce qui permet à une seule comparaison de remplacer un parcours de toutes les lettres.

Q: En quoi le problème « Minimum Window Substring » diffère-t-il de la recherche d’un anagramme dans une chaîne de caractères ?

Un anagramme contient exactement les lettres de t et aucune autre, donc la fenêtre a une longueur fixe de m et se déplace d’un pas à la fois. Ici, la fenêtre peut contenir des caractères supplémentaires, donc sa longueur fait partie de la réponse : elle s’agrandit vers la droite jusqu’à couvrir t et rétrécit vers la gauche tant qu’elle le couvre encore.

DifficileFenêtre glissante Hachage

+10

Vous recevez deux chaînes, s et t. Trouvez la plus courte sous-chaîne de s, une suite de caractères consécutifs, qui contient chaque caractère de t, en tenant compte des répétitions : si t contient deux fois une lettre, la sous-chaîne doit la contenir au moins deux fois. L’ordre n’a pas d’importance, et la sous-chaîne peut aussi contenir d’autres caractères.

Si plusieurs sous-chaînes ont la même longueur minimale, renvoyez celle qui se trouve le plus à gauche. Si aucune sous-chaîne de s ne contient tous les caractères de t, renvoyez une chaîne vide.

Fonction

minWindow(s: string, t: string) → string

sstring: la chaîne dans laquelle effectuer la recherche
tstring: les caractères que la fenêtre doit contenir, avec répétitions
Renvoiestring: la sous-chaîne de s la plus courte, puis la plus à gauche, qui contient tous les caractères de t, ou une chaîne vide

Contraintes

1 ≤ s.length ≤ 5 × 10⁴
1 ≤ t.length ≤ 10⁴
s et t contiennent uniquement des lettres anglaises. Les lettres majuscules et minuscules sont des caractères différents.
Lorsqu’il existe plusieurs sous-chaînes les plus courtes, la réponse est celle qui se trouve le plus à gauche ; lorsqu’il n’en existe aucune, c’est "".

Exemples

Entrée: s = "mappingtheplan"t = "nap"
Sortie: "plan"
Explication: En lisant de gauche à droite, la première fenêtre qui contient un n, un a et un p est appin, longue de cinq caractères. plan, à la fin, contient les trois en quatre caractères, et aucune séquence de trois caractères ne les contient.

Entrée: s = "banana"t = "aan"
Sortie: "ana"
Explication: t demande deux copies de a et un n. ana à l’index 1 contient exactement cela. Un deuxième ana commence à l’index 3, et c’est le premier qui l’emporte.

Entrée: s = "Coddy"t = "cd"
Sortie: ""
Explication: Le seul C dans Coddy est en majuscule, et les lettres majuscules et minuscules sont des caractères différents. Aucune sous-chaîne ne contient de c minuscule, donc la réponse est la chaîne vide.

+17 tests cachés à la soumission

Pour aller plus loin

Lorsque t n’utilise que quelques lettres et que s est long, la majeure partie de s ne peut jamais être utile. Peux-tu faire en sorte que la fenêtre ne se déplace qu’entre les positions qui contiennent une lettre de t ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La réponse dépend du nombre de chaque caractère que contient une fenêtre, et non de leur ordre, et la meilleure fenêtre peut commencer n’importe où. Essayer chaque début avec chaque fin signifie O(n²) fenêtres. L’astuce consiste à utiliser une fenêtre dont les bords ne se déplacent que vers l’avant : le bord droit l’agrandit jusqu’à ce qu’elle couvre t, le bord gauche la rétrécit tant que c’est le cas, et un compteur de caractères manquants vous indique en une seule étape si elle couvre t.

Agrandissez une fenêtre à partir de chaque position de départ

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Fixez le début de la sous-chaîne. Puis agrandissez-la d’un caractère à la fois, en comptant chaque caractère qu’elle contient, et vérifiez après chaque étape si elle couvre t : pour chacune des u lettres différentes utilisées dans t, la fenêtre doit contenir au moins autant d’occurrences que t. La première fin qui satisfait cette condition donne la plus courte fenêtre couvrante pour ce début, car toutes les fenêtres plus courtes ayant le même début ont été vérifiées auparavant et ne satisfaisaient pas la condition. Arrêtez-vous là.

Faites cela pour chaque début et gardez la fenêtre la plus courte. Les débuts sont essayés de gauche à droite et une fenêtre ne remplace la meilleure que si elle est strictement plus courte ; parmi les fenêtres de même longueur, celle qui commence le plus à gauche est donc conservée.

Cette méthode est lente lorsque les fenêtres sont longues ou qu’elles n’existent pas. Si l’unique Z de s se trouve tout à la fin et que t en demande un, chaque début parcourt la chaîne jusqu’à la fin : environ n²/2 étapes, soit 1.25 × 10^9 pour n = 5 × 10^4, chacune nécessitant une vérification portant sur jusqu’à 52 lettres. Il en va de même lorsqu’aucune fenêtre n’existe.

Algorithme

Comptez le nombre d’occurrences de chaque caractère demandé par t, et listez les lettres qu’il contient.
Pour chaque start, videz une table de comptage et déplacez end de start jusqu’à la fin de s, en ajoutant s[end] à la table.
Après chaque ajout, vérifiez chaque lettre de t. Si la fenêtre contient suffisamment d’occurrences de chaque lettre, comparez sa longueur à celle de la meilleure fenêtre trouvée jusque-là, conservez-la si elle est strictement plus courte, puis arrêtez de l’agrandir.
Après avoir testé tous les points de départ, renvoyez la meilleure fenêtre, ou "" si aucune ne couvre t.

def minWindow(s, t):
    need = [0] * 128  # copies of each character code that t asks for
    for ch in t:
        need[ord(ch)] += 1
    letters = [c for c in range(128) if need[c] > 0]
    best_start, best_len = 0, len(s) + 1
    for start in range(len(s)):
        have = [0] * 128  # counts inside s[start..end]
        for end in range(start, len(s)):
            have[ord(s[end])] += 1
            if all(have[c] >= need[c] for c in letters):
                # The first end that covers t gives the shortest window from this start.
                if end - start + 1 < best_len:
                    best_start, best_len = start, end - start + 1
                break
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

Fenêtre glissante qui vérifie chaque lettre

Intuition

Deux faits éliminent le redémarrage. Ajouter des caractères à une fenêtre qui couvre t fait qu’elle continue de le couvrir, et en retirer à une fenêtre qui ne couvre pas un élément ne la fera toujours pas le couvrir. Ainsi, lorsque le début se déplace vers la droite, la fin de la plus courte fenêtre couvrante peut seulement rester en place ou se déplacer vers la droite. Les deux bords peuvent avancer ensemble, sans jamais reculer.

Déplace right le long de s, en ajoutant chaque caractère à un tableau de compteurs. Chaque fois que la fenêtre couvre t, elle est candidate : enregistre-la si elle est plus courte que la meilleure, puis retire s[left], avance left et vérifie à nouveau. Répète jusqu’à ce que la fenêtre cesse de couvrir t, puis recommence à l’agrandir vers la droite.

Aucune fenêtre n’est oubliée. Considère la meilleure fenêtre, de L à R. Si left avait dépassé L avant que right n’atteigne R, une fenêtre allant de L et se terminant avant R aurait couvert t, et elle aurait été plus courte que la meilleure. Ainsi, lorsque right atteint R, la boucle de réduction fait avancer left jusqu’à L et enregistre la meilleure fenêtre. Chaque bord se déplace au plus n fois, mais chaque vérification lit jusqu’à u compteurs, un pour chaque lettre utilisée par t, même si un seul compteur a changé depuis la dernière vérification.

Algorithme

Comptez les occurrences demandées par t et listez ses lettres ; commencez avec une fenêtre vide, left = 0, et une meilleure longueur de n+1.
Déplacez right sur chaque index et ajoutez s[right] aux compteurs de la fenêtre.
Tant que chaque lettre de t est présente en quantité suffisante dans la fenêtre, enregistrez la fenêtre si elle est strictement plus courte que la meilleure, retirez s[left] des compteurs et avancez left.
Renvoyez la meilleure fenêtre, ou "" si la meilleure longueur est toujours n+1.

def minWindow(s, t):
    need = [0] * 128  # copies of each character code that t asks for
    for ch in t:
        need[ord(ch)] += 1
    letters = [c for c in range(128) if need[c] > 0]
    have = [0] * 128  # counts inside s[left..right]

    def covers():
        for c in letters:
            if have[c] < need[c]:
                return False
        return True

    left = 0
    best_start, best_len = 0, len(s) + 1
    for right in range(len(s)):
        have[ord(s[right])] += 1  # expand on the right
        while covers():  # shrink from the left while the window still covers t
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1
            have[ord(s[left])] -= 1
            left += 1
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

Fenêtre glissante avec un compteur de valeurs manquantes

Intuition

Gardez la même fenêtre et remplacez la vérification par un seul nombre. Soit need[c] le nombre d’occurrences de c demandées par t, moins le nombre d’occurrences dans la fenêtre. Une valeur positive signifie qu’il en manque encore dans la fenêtre ; une valeur négative signifie qu’elle en a en trop. Soit missing le nombre total d’occurrences manquantes dans la fenêtre, initialisé à la longueur de t. La fenêtre couvre exactement t lorsque missing vaut 0.

La mise à jour coûte une étape. Lorsque s[right] entre et que la valeur de need pour ce caractère est supérieure à 0, il comble un manque, donc missing diminue de un ; dans tous les cas, need diminue de un et peut passer sous 0, indiquant un surplus. Lorsque s[left] sort, need augmente de un et, si sa valeur est alors supérieure à 0, la fenêtre a perdu une occurrence dont t avait besoin, donc missing augmente de un. Les surplus vont et viennent sans modifier missing.

Suivons s = banana, t = aan : need commence avec a à 2, n à 1, et missing à 3. b n’est pas nécessaire. Le premier a fait passer missing à 2, le n à 1, puis le deuxième a à 0 ; bana couvre donc t. Le rétrécissement retire le b en surplus et laisse ana, trois caractères, le nouveau meilleur résultat. Retirer ce a fait repasser missing à 1. Le dernier a permet à nouveau de couvrir t avec nana, qui se réduit au deuxième ana. Il n’est pas plus court, donc le ana le plus à gauche est conservé.

Chaque caractère de s entre une fois dans la fenêtre et en sort au plus une fois, et chaque déplacement demande une quantité fixe de travail. La construction de need parcourt t une seule fois. L’ensemble de l’exécution est en O(n + m), avec un tableau de 128 compteurs comme seule mémoire supplémentaire.

Algorithme

Remplis need avec le nombre d’occurrences de t, et définis missing comme la longueur de t, left = 0 et la meilleure longueur comme n+1.
Pour chaque right : si need[s[right]] est supérieur à 0, diminue missing ; puis diminue need[s[right]].
Tant que missing vaut 0, enregistre la fenêtre si elle est strictement plus courte que la meilleure. Puis augmente need[s[left]] ; si sa valeur est alors supérieure à 0, augmente missing. Avance left.
Renvoie la meilleure fenêtre, ou "" si la meilleure longueur vaut toujours n+1.

def minWindow(s, t):
    # need[c]: copies of c that t asks for minus copies inside the window.
    # Positive means the window still lacks c; negative means it holds spares.
    need = [0] * 128
    for ch in t:
        need[ord(ch)] += 1
    missing = len(t)  # characters of t the window does not cover yet
    left = 0
    best_start, best_len = 0, len(s) + 1
    for right in range(len(s)):
        c = ord(s[right])
        if need[c] > 0:  # this copy fills a gap
            missing -= 1
        need[c] -= 1
        while missing == 0:  # the window covers t: record it, then shrink
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1
            c = ord(s[left])
            need[c] += 1
            if need[c] > 0:  # gave away a copy t needs
                missing += 1
            left += 1
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

Pièges et cas limites

La plupart des mauvaises réponses comptent la mauvaise chose ou enregistrent la fenêtre au mauvais moment.

Compter les lettres au lieu des occurrences. t = aan nécessite deux a, donc ban ne le couvre pas.
Décrémenter missing pour chaque caractère qui entre. Un troisième a est en trop ; si cela décrémente missing, le compteur atteint 0 alors que la fenêtre ne contient toujours pas le n. Décrémentez-le uniquement si need était supérieur à 0.
Incrémenter missing pour chaque caractère qui sort. Retirer un caractère en trop laisse la fenêtre couvrir t ; incrémentez-le uniquement si need devient supérieur à 0.
Enregistrer la fenêtre après la boucle de réduction. À ce stade, elle ne couvre plus t. Enregistrez-la dans la boucle, avant de retirer s[left].
Remplacer la meilleure fenêtre lorsque la nouvelle est de longueur égale. Cela renvoie la fenêtre la plus à droite parmi les plus courtes ; utilisez une comparaison strictement inférieure.
Utiliser n comme longueur « introuvable ». Lorsque la réponse correspond à tout s, sa longueur est également n. Commencez par n+1 afin que les deux cas soient différents.
Utiliser une table de 26 cases indexée par c - 'a'. Les lettres majuscules n’y rentrent pas. Utilisez une case par code de caractère.

Questions fréquentes4

Quelle est la complexité temporelle de Minimum Window Substring ?

La fenêtre glissante avec un compteur de caractères manquants s’exécute en O(n + m), où n et m sont les longueurs de s et t. La construction de la table parcourt t une fois, et chaque caractère de s entre dans la fenêtre et en sort au plus une fois, avec un coût fixe par déplacement. La mémoire supplémentaire correspond à une table contenant un compteur par code de caractère, qui n’augmente pas avec la taille des données d’entrée.

Pourquoi le bord gauche ne revient-il jamais en arrière ?

Le bord gauche dépasse une position uniquement après qu’une fenêtre commençant à cet endroit a couvert t, et qu’il s’agissait de la plus courte fenêtre couvrante depuis ce point de départ. Toute fenêtre commençant à cet endroit et se terminant plus loin est plus longue ; revenir en arrière ne pourrait donc jamais permettre de trouver une meilleure réponse. C’est pourquoi les deux bords avancent chacun une seule fois et que le travail reste linéaire.

Que compte le compteur manquant ?

C’est le nombre de copies de caractères que t demande et que la fenêtre ne contient pas encore, soit la somme des valeurs positives dans need. Il commence à la longueur de t et vaut 0 exactement lorsque la fenêtre couvre t. Les copies excédentaires ne le modifient jamais, ce qui permet à une seule comparaison de remplacer un parcours de toutes les lettres.

En quoi le problème « Minimum Window Substring » diffère-t-il de la recherche d’un anagramme dans une chaîne de caractères ?

Un anagramme contient exactement les lettres de t et aucune autre, donc la fenêtre a une longueur fixe de m et se déplace d’un pas à la fois. Ici, la fenêtre peut contenir des caractères supplémentaires, donc sa longueur fait partie de la réponse : elle s’agrandit vers la droite jusqu’à couvrir t et rétrécit vers la gauche tant qu’elle le couvre encore.

Python

def minWindow(s, t):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

s = "mappingtheplan"
t = "nap"

Attendu

"plan"

Minimum Window Substring

Fonction

Contraintes

Exemples

Indices

Solution

Agrandissez une fenêtre à partir de chaque position de départ

Fenêtre glissante qui vérifie chaque lettre

Fenêtre glissante avec un compteur de valeurs manquantes

Pièges et cas limites

Questions fréquentes4

Problèmes similaires