Minimum Window Substring

Q: En quoi Minimum Window Substring diffère-t-il de la recherche d’un anagramme dans une chaîne ?

Un anagramme contient exactement les lettres de t ; sa fenêtre a donc une longueur fixe m et glisse d’un pas à la fois. Ici, les caractères supplémentaires sont autorisés, donc la longueur fait partie de la réponse : la fenêtre s’agrandit jusqu’à couvrir t , puis rétrécit tant qu’elle le couvre encore.

DifficileFenêtre glissante Hachage

+10

On vous donne deux chaînes, s et t. Trouvez la plus courte sous-chaîne de s qui contient chaque caractère de t, en tenant compte des répétitions : si t contient une lettre deux fois, la sous-chaîne doit la contenir au moins deux fois. L’ordre n’a pas d’importance, et d’autres caractères peuvent également apparaître.

Si plusieurs sous-chaînes sont les plus courtes, renvoyez celle qui se trouve le plus à gauche. Si aucune 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, y compris les répétitions
Renvoiestring: la sous-chaîne la plus courte et, en cas d’égalité, la plus à gauche de s 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 ne contiennent que des lettres anglaises. Les lettres majuscules et minuscules sont des caractères différents.
Lorsque plusieurs sous-chaînes sont 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: La première fenêtre en partant de la gauche qui contient un n, un a et un p est appin, cinq caractères. plan contient les trois en quatre caractères, et aucune séquence de trois ne le fait.

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

Entrée: s = "Coddy"t = "cd"
Sortie: ""
Explication: Le C dans Coddy est une majuscule, un caractère différent de c. Aucune sous-chaîne ne contient de c minuscule, donc la réponse est la chaîne vide.

Pour aller plus loin

Lorsque t comporte peu de lettres et que s est long, la majeure partie de s n’a jamais d’importance. Peux-tu faire en sorte que la fenêtre ne saute 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

Seuls les comptes des caractères dans une fenêtre importent, pas leur ordre. Déplace le bord droit jusqu’à ce que la fenêtre couvre t, puis le bord gauche tant qu’elle le couvre encore ; aucun des deux bords ne revient en arrière. Un compteur des caractères manquants te permet de savoir en une seule étape si la fenêtre couvre t.

Agrandissez une fenêtre à partir de chaque début

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Fixez un début et agrandissez la fenêtre d’un caractère à la fois, en comptant chaque caractère. Après chaque étape, vérifiez chacune des u lettres utilisées dans t. La première extrémité qui convient donne la plus courte fenêtre couvrante à partir de ce début ; arrêtez-vous donc là. Les débuts sont parcourus de gauche à droite et seule une fenêtre strictement plus courte remplace la meilleure, les ex æquo conservent donc celle qui est la plus à gauche.

Si aucune fenêtre n’existe, chaque début parcourt s jusqu’à la fin : environ n²/2 étapes, soit 1.25 × 10^9 pour n = 5 × 10^4.

Algorithme

Comptez le nombre d’occurrences de chaque lettre demandée par t.
Pour chaque start, réinitialisez une table de comptage et déplacez end vers la droite en ajoutant s[end].
Lorsque la fenêtre contient suffisamment d’occurrences de chaque lettre, conservez-la si elle est strictement plus courte que la meilleure fenêtre, puis passez au start suivant.
Retournez la meilleure fenêtre, ou "" si aucune ne contenait 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

Ajouter des caractères à une fenêtre couvrante la maintient couvrante, et retirer des caractères d’une fenêtre à laquelle il manque quelque chose la laisse incomplète. Ainsi, lorsque le début se déplace vers la droite, la fin de la plus courte fenêtre couvrante ne se déplace jamais vers la gauche.

Aucune fenêtre n’est ignorée. Considère la meilleure fenêtre, de L à R. Pour que left dépasse L avant que right atteigne R, une fenêtre plus courte commençant à L devrait couvrir t. Ainsi, lorsque right atteint R, le rétrécissement fait avancer left jusqu’à L et enregistre cette fenêtre.

Chaque extrémité se déplace au plus n fois, mais chaque vérification lit jusqu’à u compteurs : O(n·u).

Algorithme

Comptez les occurrences demandées par t ; définissez left = 0 et la meilleure longueur à n+1.
Pour chaque right, ajoutez s[right] aux compteurs de la fenêtre.
Tant que chaque lettre de t est présente en quantité suffisante, enregistrez la fenêtre si elle est strictement plus courte, supprimez s[left] et avancez left.
Retournez 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

Remplace le balayage 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 négative indique des occurrences en surplus. Soit missing le nombre d’occurrences qui manquent encore à la fenêtre, initialisé à la longueur de t. La fenêtre couvre exactement t lorsque missing vaut 0.

Un caractère qui entre alors que son need est supérieur à 0 comble un manque, donc missing diminue. La suppression d’un caractère qui fait passer son need au-dessus de 0 crée un manque, donc missing augmente. Les occurrences en surplus n’ont aucun effet sur cette valeur. Pour banana avec t = aan, missing atteint d’abord 0 pour bana, et la suppression du b en surplus laisse ana, qui couvre toujours t.

Chaque caractère entre et sort une seule fois, pour un coût fixe : temps O(n + m), avec un tableau de 128 compteurs.

Algorithme

Remplis need avec les occurrences de t ; 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. Augmente need[s[left]] ; s’il est maintenant supérieur à 0, augmente missing. Avance left.
Retourne 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

Compter les lettres au lieu des occurrences. t = aan nécessite deux a, donc ban ne convient pas.
Modifier missing pour chaque caractère qui entre ou sort. Un a en trop est alors compté, et missing peut atteindre 0 alors que la fenêtre ne contient pas le n.
Remplacer la meilleure fenêtre lorsque les longueurs sont égales. Dans le deuxième exemple, cela renvoie le ana à l’indice 3.
Utiliser n comme longueur signifiant « introuvable ». Lorsque la réponse correspond à tout s, sa longueur est également n ; commencez à n+1.
Un tableau de 26 cases indexé par c - 'a'. Les lettres majuscules, comme dans le troisième exemple, n’y tiennent pas.

Questions fréquentes3

Quelle est la complexité temporelle de Minimum Window Substring ?

La fenêtre à compteur des caractères manquants s’exécute en O(n + m), où n et m sont les longueurs de s et de t. La construction de la table lit t une seule fois, et chaque caractère de s entre et sort de la fenêtre au plus une fois. La mémoire supplémentaire correspond à un compteur par code de caractère.

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

Le bord gauche ne franchit une position qu’une fois que la fenêtre qui commence à cet endroit a couvert t, et cette fenêtre était la plus courte fenêtre couvrante à partir de ce point de départ. Toute fenêtre partant de là et se terminant plus tard est plus longue, donc revenir en arrière ne peut jamais donner une meilleure réponse.

En quoi Minimum Window Substring diffère-t-il de la recherche d’un anagramme dans une chaîne ?

Un anagramme contient exactement les lettres de t ; sa fenêtre a donc une longueur fixe m et glisse d’un pas à la fois. Ici, les caractères supplémentaires sont autorisés, donc la longueur fait partie de la réponse : la fenêtre s’agrandit jusqu’à couvrir t, puis rétrécit tant qu’elle le couvre encore.

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

Test #1

Test #2

Test #3

Arguments

s = "mappingtheplan"
t = "nap"

Résultat attendu

"plan"

Minimum Window Substring

Fonction

Contraintes

Exemples

Indices

Solution

Agrandissez une fenêtre à partir de chaque début

Fenêtre glissante qui vérifie chaque lettre

Fenêtre glissante avec un compteur de valeurs manquantes

Pièges et cas limites

Questions fréquentes3

Problèmes similaires