Maîtrisez Minimum Window Substring avec l’invariant, les doublons et la fenêtre minimale. Une explication claire pour réussir en entretien.
La plupart des candidats qui restent muets sur ce problème en entretien ne restent pas muets parce qu’ils ont oublié l’algorithme. Ils restent muets parce qu’ils n’ont jamais séparé les deux questions que le problème pose réellement : comment savoir si une fenêtre est valide, et comment savoir si c’est la plus petite fenêtre valide ? Ce sont deux questions différentes, et les confondre explique pourquoi les explications de minimum window substring finissent si souvent en vagues généralités au moment même où l’interviewer se penche en avant.
La bonne nouvelle, c’est qu’une fois que vous pouvez énoncer l’invariant de validité de la fenêtre en français courant, toute la solution cesse de ressembler à une astuce mémorisée et commence à ressembler à une conséquence inévitable de la règle que vous connaissez déjà. C’est autour de ce basculement que ce guide est construit.
Ce que Minimum Window Substring vous demande réellement de prouver
Le problème ne consiste pas à « trouver une sous chaîne » — il s’agit de « prouver que celle ci est la plus petite valide »
L’énoncé standard est le suivant : étant donné la chaîne `s` et la chaîne `t`, trouver la sous-chaîne de longueur minimale de `s` qui contient tous les caractères de `t`. Assez simple à lire. L’erreur structurelle la plus fréquente chez les candidats est de traiter cela comme un problème de recherche, alors qu’il s’agit en réalité d’un problème de preuve. Trouver une fenêtre valide est facile — n’importe quelle fenêtre qui couvre tous les caractères de `t` convient. La difficulté consiste à prouver que la fenêtre que vous retournez est la plus petite, ce qui exige de définir formellement ce que signifie « valide » avant même d’écrire la moindre ligne de code.
Les candidats qui se jettent directement sur la boucle à deux pointeurs sans définir d’abord la validité produisent des explications bancales. Ils peuvent décrire ce que fait le code, mais ils ne peuvent pas expliquer pourquoi il est sûr de faire avancer le pointeur gauche, ni pourquoi le minimum trouvé est réellement le minimum. C’est cette faille que les interviewers perçoivent.
À quoi cela ressemble en pratique
Prenons l’exemple canonique : `s = "ADOBECODEBANC"`, `t = "ABC"`. Il existe plusieurs fenêtres valides dans cette chaîne — `"ADOBEC"` est valide, `"DOBECODEBA"` est valide, `"BANC"` est valide. Le problème n’est pas d’en identifier une quelconque. Le problème est d’arriver à `"BANC"` et de pouvoir affirmer, avec confiance, que rien de plus court n’existe. Cette affirmation nécessite un argument structurel, pas seulement un parcours de la chaîne. L’algorithme obtient le minimum en s’étendant jusqu’à ce que la fenêtre soit valide, puis en se rétrécissant autant que la validité le permet, tout en enregistrant la meilleure fenêtre trouvée à chaque état valide. Chaque étape de cette boucle découle de l’invariant — et c’est précisément ce que l’interviewer attend que vous formuliez.
Énoncez l’invariant de validité de la fenêtre avant de toucher au code
L’unique invariant qui maintient l’ensemble cohérent
Voici l’invariant, formulé simplement : une fenêtre est valide si et seulement si, pour chaque caractère `c` dans `t`, le nombre de fois où `c` apparaît dans la fenêtre courante est supérieur ou égal au nombre de fois où `c` est requis par `t`. Pas seulement que le caractère est présent. Pas seulement que les bons caractères sont quelque part dans la fenêtre. Les comptes doivent satisfaire ou dépasser les exigences, pour chaque caractère, simultanément.
C’est la phrase qu’il vaut la peine d’écrire au tableau avant toute autre chose. Elle fait de la validité un état binaire, vérifiable, plutôt qu’un ressenti vague. Et c’est le fondement sur lequel repose tout le reste de l’algorithme.
À quoi cela ressemble en pratique
L’implémentation standard suit cela à l’aide de deux cartes de fréquences : `need`, qui stocke le nombre requis de chaque caractère de `t`, et `window`, qui stocke le nombre observé de chaque caractère dans la fenêtre courante. Une troisième variable — appelez-la `matched` — compte combien de caractères distincts de `t` sont entièrement satisfaits (c’est-à-dire `window[c] >= need[c]`). La fenêtre est valide exactement lorsque `matched == len(need)`.
C’est important parce que la validité est un état dans lequel vous entrez et que vous quittez au fil du déplacement des pointeurs. Lorsque vous ajoutez un caractère à droite et que `window[c]` passe de `need[c] - 1` à `need[c]`, vous incrémentez `matched`. Lorsque vous retirez un caractère à gauche et que `window[c]` tombe en dessous de `need[c]`, vous décrémentez `matched`. L’invariant est toujours soit satisfait, soit non — il n’y a pas d’ambiguïté, et c’est précisément ce qui rend l’algorithme fiable.
Pourquoi l’interviewer attache plus d’importance à cela qu’à la forme de votre code
Un candidat qui récite la boucle à deux pointeurs sans pouvoir expliquer pourquoi elle est correcte est, du point de vue de l’interviewer, quelqu’un qui a mémorisé une solution. Un candidat qui énonce d’abord l’invariant puis dérive la boucle à partir de lui est quelqu’un qui comprend le problème. La syntaxe de l’implémentation peut être retrouvée sous pression. Le raisonnement, non — sauf si vous l’avez vraiment intégré.
L’invariant, c’est l’histoire de la correction. Quand un interviewer demande « pourquoi est-il sûr de faire avancer le pointeur gauche ici ? », la réponse est : parce que la fenêtre est encore valide, donc vous n’avez rien perdu de requis. Cette réponse ne vient naturellement que si vous avez commencé par l’invariant, pas par le code. Selon Introduction to Algorithms (CLRS), le raisonnement par invariant est précisément ce qui distingue un algorithme correct d’un algorithme qui donne seulement le bon résultat sur les cas de test que vous avez essayés.
Gérez les caractères dupliqués dans t sans casser les comptes
Pourquoi « le caractère est présent » est le mauvais critère
Le bug le plus courant dans les solutions du problème de la sous-chaîne minimale n’est pas une erreur de syntaxe. C’est une erreur conceptuelle : traiter l’appartenance d’un caractère comme une couverture. Si `t = "AABC"`, une fenêtre qui contient un `A`, un `B` et un `C` n’est pas valide. Elle a besoin de deux `A`. Un candidat qui vérifie `'A' in window` au lieu de `window['A'] >= need['A']` produira une solution qui passe les cas simples et échoue dès que des doublons apparaissent.
C’est exactement là que les interviewers creusent. Ils vous demanderont de dérouler un cas avec des caractères dupliqués dans `t`, et si votre modèle mental est « est-ce que la fenêtre contient tous les caractères de `t` ? », vous donnerez la mauvaise réponse.
À quoi cela ressemble en pratique
Supposons que `t = "AABC"`. La carte `need` est `{'A': 2, 'B': 1, 'C': 1}`. Une fenêtre contenant `"ABC"` a `window = {'A': 1, 'B': 1, 'C': 1}`. Le compte de `A` est 1, mais l’exigence est 2. L’invariant n’est pas satisfait — `matched` ne doit augmenter pour `A` que lorsque `window['A']` atteint 2, pas lorsqu’il atteint 1. Tant que ce deuxième `A` n’entre pas dans la fenêtre, celle-ci est invalide, peu importe combien d’autres caractères elle couvre.
Le compteur `matched` gère cela proprement : vous ne l’incrémentez que lorsque `window[c]` passe de `need[c] - 1` à exactement `need[c]`. Une occurrence de `A` ne déclenche pas l’incrément. La deuxième, si. Voilà pourquoi l’approche par comptage n’est pas une optimisation — c’est une condition de correction.
La manière simple de l’expliquer à voix haute en entretien
La distinction verbale est simple : fréquence requise versus fréquence observée. Si la fréquence observée de chaque caractère atteint ou dépasse la fréquence requise, la fenêtre est valide. Si la fréquence observée d’un caractère est inférieure à sa fréquence requise, la fenêtre est invalide. Formuler les choses ainsi rend la logique des doublons évidente plutôt qu’exceptionnelle. L’explication de GeeksforGeeks sur la technique du sliding window couvre la mise en place des cartes de fréquences, même si le cadrage par invariant y est rarement aussi explicite.
Étendez à droite, puis rétrécissez à gauche uniquement tant que la fenêtre reste valide
Pourquoi la phase de rétrécissement est sûre, et à quel moment elle ne l’est plus
C’est l’étape de correction que la plupart des candidats omettent. Réduire le pointeur gauche est sûr pour une seule raison : la fenêtre reste valide après la réduction. Dès que la fenêtre devient invalide — c’est-à-dire lorsque `matched` passe en dessous de `len(need)` — vous devez arrêter de rétrécir. Continuer au-delà de ce point éliminerait un caractère requis, et la fenêtre ne contiendrait plus tout `t`. Le minimum enregistré au dernier état valide est le vrai minimum pour cette position du pointeur droit.
Ce n’est pas une heuristique. C’est une conséquence directe de l’invariant. Si l’invariant est satisfait, le rétrécissement est sûr. S’il ne l’est pas, il ne l’est pas. L’algorithme est correct parce qu’il respecte systématiquement cette limite.
À quoi cela ressemble en pratique
Le déroulé, en termes simples : faites avancer le pointeur droit jusqu’à ce que la fenêtre soit valide (`matched == len(need)`). Une fois valide, enregistrez la taille courante de la fenêtre comme candidate au minimum. Puis faites avancer le pointeur gauche — en mettant à jour `window` et `matched` au passage — et continuez à rétrécir tant que la fenêtre reste valide, en enregistrant une nouvelle candidate à chaque fois. Lorsque la fenêtre devient invalide, arrêtez de rétrécir et reprenez l’expansion à droite. Répétez jusqu’à ce que le pointeur droit ait parcouru toute la chaîne `s`.
Ce motif de problème d’entretien basé sur le sliding window comporte deux phases imbriquées : expansion jusqu’à validité, puis rétrécissement jusqu’au minimum. Aucune phase n’est facultative. La phase d’expansion trouve la validité. La phase de rétrécissement trouve la minimalité. Les deux sont nécessaires pour résoudre le problème correctement.
L’aspect que les gens survolent et qui finit par les pénaliser
Le mode d’échec consiste à s’arrêter à la première fenêtre valide au lieu de continuer à la rétrécir. Un candidat qui enregistre la première fenêtre valide et passe à autre chose obtiendra la bonne réponse sur des exemples simples, mais échouera sur des chaînes où la fenêtre minimale apparaît après plusieurs cycles d’expansion et de contraction. La boucle `while matched == len(need)` n’est pas un détail — c’est le mécanisme qui trouve le minimum, et non simplement une fenêtre valide. L’omettre produit une solution en apparence correcte mais fondamentalement défectueuse.
Déroulez ADOBECODEBANC jusqu’à ce que le motif cesse d’avoir l’air aléatoire
Pourquoi ADOBECODEBANC est le bon exemple à mémoriser
Cette chaîne est l’exemple standard pour une raison : elle oblige les deux phases de l’algorithme à se déployer de manière visible. Elle est assez longue pour que la phase d’expansion produise plusieurs fenêtres valides, et la phase de rétrécissement modifie réellement la réponse. Si vous pouvez la parcourir en détail et expliquer chaque transition d’état, vous pouvez expliquer l’algorithme. Selon l’énoncé du problème Minimum Window Substring sur LeetCode (Problème 76), la sortie attendue pour `s = "ADOBECODEBANC"`, `t = "ABC"` est `"BANC"` — et y parvenir exige de comprendre pourquoi les fenêtres valides précédentes ne sont pas minimales.
À quoi cela ressemble en pratique
Voici la trace essentielle, avec deux pointeurs et l’état de la carte de fréquences :
- Le pointeur droit s’étend : `A` → `D` → `O` → `B` → `E` → `C`. À `C`, la fenêtre est `"ADOBEC"`, tout `ABC` est couvert. `matched = 3`. Première fenêtre valide, longueur 6.
- Rétrécissez à gauche : retirez `A`. `window['A']` tombe à 0, en dessous de `need['A'] = 1`. `matched` passe à 2. Fenêtre invalide. Arrêtez de rétrécir.
- Le pointeur droit s’étend : `O` → `D` → `E` → `B`. La fenêtre est `"DOBECODEB"`. Il manque toujours `A`. Continuez à étendre.
- Le pointeur droit atteint `A`. La fenêtre est `"DOBECODEBA"`. `matched = 3` à nouveau. Valide. Longueur 10 — pire que 6.
- Rétrécissez à gauche : retirez `D`, `O`, `B`, `E`, `C`, `O`, `D`, `E`. Chaque retrait est sûr parce que `A`, `B`, `C` sont toujours couverts. La fenêtre se réduit à `"BA"` — mais `C` a disparu. Invalide.
- Le pointeur droit s’étend : `N` → `C`. La fenêtre est `"BANC"`. `matched = 3`. Valide. Longueur 4 — nouveau minimum.
- Rétrécissez à gauche : retirez `B`. `window['B']` tombe sous `need['B']`. Invalide. Stop.
- Le pointeur droit est épuisé. Retournez `"BANC"`.
Le moment où la fenêtre devient plus petite et plus intelligente
La transition cruciale se produit lorsque l’algorithme arrive à `"BANC"` après la deuxième phase d’expansion. À ce moment-là, la fenêtre est valide, de longueur 4, ce qui bat le meilleur précédent de 6. L’algorithme l’enregistre. Puis il tente de rétrécir encore, perd immédiatement `B`, et s’arrête. Cette séquence — valide, enregistrer, rétrécir jusqu’à l’invalidité — est l’invariant en action. La réponse `"BANC"` n’est pas une supposition. C’est la conséquence d’une règle appliquée de manière cohérente.
Donnez la réponse comme si vous la pensiez vraiment en 60 secondes d’entretien
La version qui sonne assurée plutôt qu’apprise par cœur
Voici à quoi ressemble une explication d’entretien sur minimum window substring quand le candidat maîtrise l’invariant :
« L’objectif est de trouver la plus courte sous-chaîne de `s` qui contient chaque caractère de `t` avec la fréquence requise. Je vais utiliser deux pointeurs et une carte de fréquences. L’invariant clé est le suivant : une fenêtre est valide lorsque le nombre observé de chaque caractère de `t` atteint ou dépasse le nombre requis. Je le suis avec un compteur `matched` — il augmente lorsqu’un caractère atteint exactement son seuil requis, et diminue lorsqu’il passe en dessous.
La boucle comporte deux phases : on étend le pointeur droit jusqu’à ce que la fenêtre soit valide, puis on rétrécit le pointeur gauche tant que la validité tient, en enregistrant la taille de la fenêtre à chaque fois. Le minimum parmi tous les états valides est la réponse. La complexité temporelle est O(n + m) — chaque pointeur avance au plus n fois, et les cartes de fréquences sont bornées par la taille de l’alphabet. L’espace est O(m) pour les cartes, ou O(1) si on utilise un tableau fixe de 128 cases pour l’ASCII. »
À quoi cela ressemble en pratique
Remarquez ce que cette explication fait : elle commence par l’objectif, énonce explicitement l’invariant, décrit la variable d’état, explique la boucle en deux phases et conclut par la complexité. Elle ne commence pas par « je vais utiliser un sliding window » en espérant que l’interviewer remplira les blancs. L’invariant apparaît dès la deuxième phrase, pas en annexe. Cet ordre montre que le candidat comprend la correction, pas seulement l’implémentation.
Connaissez les bugs qui font échouer de bonnes solutions en entretien
Les erreurs classiques : off by one, comptes obsolètes et oubli des doublons
Trois bugs représentent la majorité des échecs sur ce problème.
Appartenance au lieu de comptage. Utiliser `c in window` au lieu de `window[c] >= need[c]` pour vérifier la validité. Échoue immédiatement dès que `t` contient des caractères dupliqués.
Oublier de décrémenter `matched` lors du rétrécissement. Retirer un caractère à gauche, mettre à jour `window[c]`, mais oublier de vérifier si `window[c]` est passé sous `need[c]` et de décrémenter `matched` en conséquence. La fenêtre semble valide plus longtemps qu’elle ne l’est réellement, et le minimum est enregistré de travers.
Enregistrer la meilleure fenêtre en dehors de l’état valide. Mettre à jour la réponse minimale lorsque `matched < len(need)` — généralement parce que le candidat teste le nouveau minimum au mauvais moment dans la boucle, avant d’avoir confirmé la validité.
À quoi cela ressemble en pratique
Le bug d’appartenance produit une fenêtre comme `"ABC"` lorsque `t = "AABC"` et la déclare valide. Le bug des comptes obsolètes produit une boucle de rétrécissement qui continue au-delà du point de validité, supprime un caractère requis et enregistre un minimum qui ne contient pas réellement tout `t`. Le bug de mauvais placement enregistre une fenêtre trop grande ou trop petite parce que la mise à jour survient au mauvais moment dans le déroulé du programme.
Chacun de ces problèmes est une erreur structurelle, pas une faute de frappe. Ils viennent d’un modèle flou de ce que signifie la validité, pas d’un code maladroit.
Le rappel dont la plupart des candidats ont besoin
Si vous avez commis l’une de ces erreurs, ce n’est pas parce que vous êtes mauvais en algorithmes. C’est parce que vous avez commencé par la forme du code plutôt que par l’invariant. Une fois l’invariant clair — valide signifie que toutes les fréquences requises sont satisfaites — chacun de ces bugs devient manifestement faux avant même l’exécution du code.
Expliquez la complexité sans donner l’impression de réciter une fiche mémo
Pourquoi c’est linéaire alors que les pointeurs bougent beaucoup
La complexité temporelle est O(n + m), où n est la longueur de `s` et m celle de `t`. L’argument est simple : le pointeur gauche et le pointeur droit avancent chacun au plus n fois, et ne reculent jamais. Le nombre total d’opérations sur les pointeurs est borné par 2n. La préparation initiale de la carte `need` est en O(m). Au total, cela donne O(n + m). L’algorithme est linéaire non pas grâce à une astuce brillante, mais à cause d’une propriété structurelle : deux pointeurs avec un état de carte de fréquences, où chaque pointeur est monotone croissant.
À quoi cela ressemble en pratique
La complexité spatiale est O(|Σ|), où Σ est l’ensemble des caractères. Pour une carte de fréquences implémentée par une table de hachage, l’espace est borné par le nombre de caractères distincts dans `s` et `t`. En pratique, cela représente au plus 52 pour des entrées alphabétiques sensibles à la casse, ou 128 pour l’ASCII complet.
Quand un tableau de taille fixe bat une table de hachage
Si l’entrée est garantie ASCII, un tableau fixe de longueur 128 est plus rapide qu’une table de hachage en pratique : pas de hachage, pas de gestion des collisions, accès direct par index. Si l’entrée peut être en Unicode — des points de code arbitraires — une table de hachage est nécessaire car l’espace des caractères est trop grand pour un tableau fixe. Connaître cette distinction et savoir l’exprimer clairement montre que vous avez réfléchi aux compromis d’implémentation réels, pas seulement à la complexité théorique.
Réutilisez le même schéma sur les bons problèmes, et évitez le sur les mauvais
Quand ce schéma s’applique, et quand il ne s’applique pas
Le pattern d’entretien du sliding window s’applique lorsque : la condition de validité dépend de la fréquence des caractères dans une fenêtre contiguë, la fenêtre peut être étendue et contractée en faisant avancer deux pointeurs, et la meilleure réponse est obtenue en minimisant ou maximisant la taille de la fenêtre sous contrainte de validité. Minimum Window Substring remplit ces trois conditions.
Il ne s’applique pas lorsque : l’ordre des caractères à l’intérieur de la fenêtre compte (problèmes de sous-séquence), la validité exige une correspondance non contiguë, ou la contrainte porte sur autre chose que la fréquence des caractères. Confondre les problèmes de sous-chaîne et de sous-séquence est une erreur de classification très fréquente.
À quoi cela ressemble en pratique
La détection d’anagrammes dans une chaîne (trouver tous les indices de départ où une permutation de `t` apparaît dans `s`) utilise la même structure de carte de fréquences et de deux pointeurs, mais la condition de validité est plus stricte : des comptes exacts, pas seulement des comptes supérieurs ou égaux, et une taille de fenêtre fixe. Minimum Window Subsequence ressemble superficiellement à ce problème, mais est fondamentalement différent : il exige que les caractères apparaissent dans l’ordre, ce qui casse complètement la logique de rétrécissement à gauche et nécessite une autre approche.
La frontière est claire dès lors que vous posez la bonne question : la validité dépend-elle de la fréquence dans une fenêtre contiguë, ou l’ordre à l’intérieur de la fenêtre compte-t-il ? Si l’ordre compte, ce schéma ne s’applique pas.
La leçon réellement transférable que les interviewers recherchent
La vraie compétence testée n’est pas de savoir si vous avez mémorisé l’algorithme de minimum window substring. C’est votre capacité à identifier l’invariant qui gouverne un problème, à construire une machine d’état autour de lui, et à raisonner sur la correction à partir de cette base. Cette compétence se transfère à tous les problèmes de sliding window, et à une classe bien plus large de problèmes où l’idée clé consiste à définir ce que signifie « valide » avant d’écrire la moindre ligne de code. Selon Algorithm Design Manual de Skiena, la capacité à formuler les invariants d’un problème est un différenciateur constant entre les candidats qui résolvent les problèmes et ceux qui se contentent d’expliquer des solutions.
Comment Verve AI peut vous aider à préparer votre entretien sur Minimum Window Substring
La partie la plus difficile de ce problème n’est pas d’écrire le code. C’est d’expliquer l’invariant à voix haute, sous pression, à quelqu’un qui cherche activement les failles. C’est une compétence de performance, et les compétences de performance se travaillent avec des répétitions en conditions réelles — pas avec davantage de lecture.
Verve AI Interview Copilot est conçu exactement pour combler cet écart. Il écoute en temps réel votre explication orale et répond à ce que vous avez réellement dit, et non à une consigne pré-écrite. Lorsque vous dites « j’utilise un sliding window » puis vous vous arrêtez là, Verve AI Interview Copilot peut rebondir comme le ferait un vrai interviewer : « Pourquoi est-il sûr de rétrécir le pointeur gauche ? » — et vous devez répondre, en direct, avec l’invariant que vous maîtrisez ou non. C’est cette répétition qui compte. Verve AI Interview Copilot reste également invisible pendant les sessions de partage d’écran au niveau du système d’exploitation, donc si vous faites un mock avec un pair ou un coach, l’outil est présent sans devenir une distraction. L’explication de 60 secondes de la section 6 mérite d’être répétée à voix haute au moins cinq fois avant votre entretien. Verve AI Interview Copilot est le moyen le plus rapide d’obtenir un retour honnête et immédiat sur le fait que votre discours sonne comme une compréhension réelle ou comme une récitation.
FAQ
Q : Qu’est-ce que l’invariant de Minimum Window, et comment savoir si une fenêtre est valide ?
Une fenêtre est valide lorsque le nombre observé de chaque caractère de `t` atteint ou dépasse le nombre requis — pas seulement que le caractère est présent, mais qu’il apparaît au moins autant de fois que `t` l’exige. Vous suivez cela avec un compteur `matched` qui vaut `len(need)` lorsque l’invariant est entièrement satisfait. Si `matched < len(need)`, la fenêtre est invalide quelle que soit sa taille.
Q : Comment les doublons dans `t` modifient-ils la logique de comptage ?
Les doublons signifient que vous ne pouvez pas vous contenter de tests d’appartenance — vous devez comparer la fréquence observée à la fréquence requise pour chaque caractère. Si `t = "AABC"`, une fenêtre a besoin de deux `A` pour satisfaire l’exigence sur `A`. Le compteur `matched` s’incrémente pour `A` seulement lorsque `window['A']` atteint `need['A'] = 2`, pas lorsqu’elle atteint 1. Un seul `A` dans la fenêtre ne rend pas la fenêtre valide.
Q : Comment rétrécir le pointeur gauche sans casser la correction ?
Vous ne rétrécissez que tant que la fenêtre reste valide — c’est-à-dire tant que `matched == len(need)`. À chaque fois que vous retirez un caractère à gauche, vous mettez à jour `window[c]` et vérifiez si `window[c]` est passé sous `need[c]`. Si c’est le cas, vous décrémentez `matched` et vous arrêtez de rétrécir. L’invariant garantit que chaque fenêtre enregistrée pendant la phase de rétrécissement est réellement valide, donc le minimum parmi elles est un vrai minimum.
Q : À quoi ressemblerait une explication d’entretien propre en 60 secondes ?
Commencez par l’objectif : trouver la sous-chaîne la plus courte de `s` contenant tous les caractères de `t` aux fréquences requises. Énoncez l’invariant : une fenêtre est valide lorsque le nombre observé de chaque caractère atteint sa fréquence requise. Décrivez le mécanisme : un compteur `matched` qui suit combien de caractères sont entièrement satisfaits. Expliquez la boucle : étendre à droite jusqu’à validité, rétrécir à gauche tant que c’est valide, enregistrer le minimum à chaque état valide. Terminez par la complexité : O(n + m) en temps, O(|Σ|) en espace. C’est l’explication complète, dans cet ordre.
Q : Quelles sont les erreurs les plus fréquentes sur ce problème ?
Trois erreurs dominent : utiliser l’appartenance (`c in window`) au lieu de la comparaison de fréquences (`window[c] >= need[c]`), oublier de décrémenter `matched` lorsqu’un caractère passe sous le seuil requis pendant la phase de rétrécissement, et enregistrer la meilleure fenêtre au mauvais moment dans la boucle — avant d’avoir confirmé que la fenêtre est valide. Les trois proviennent d’une définition floue de la validité, pas d’erreurs de codage.
Q : Comment ce schéma se transpose-t-il à d’autres questions d’entretien sur le sliding window ?
Le schéma s’applique lorsque la validité dépend de la fréquence des caractères dans une fenêtre contiguë et que la meilleure réponse minimise ou maximise la taille de la fenêtre. La détection d’anagrammes utilise la même structure avec des comptes exacts et une taille de fenêtre fixe. Minimum Window Subsequence ressemble à ce problème mais exige un appariement ordonné, ce qui casse la logique de rétrécissement à gauche. La compétence transférable consiste à se demander : la validité dépend-elle de la fréquence dans une fenêtre contiguë, ou l’ordre à l’intérieur de la fenêtre compte-t-il ?
Q : Comment dérouler ADOBECODEBANC pas à pas ?
Étendez à droite jusqu’à `"ADOBEC"` — première fenêtre valide, longueur 6. Rétrécissez à gauche : retirez `A`, la fenêtre devient invalide, stop. Étendez à droite jusqu’à `"DOBECODEBA"` — valide à nouveau, longueur 10, moins bien. Rétrécissez à gauche autant que la validité le permet. Étendez à droite jusqu’à `"BANC"` — valide, longueur 4, nouveau minimum. Essayez de rétrécir : retirez `B`, invalide, stop. Le pointeur droit est épuisé. Retournez `"BANC"`. L’essentiel est de suivre `matched` à chaque étape pour confirmer quand la validité est atteinte et quand elle est perdue.
Conclusion
Ce problème n’est pas un piège. Il ne l’a jamais été. S’il donne cette impression, c’est parce que la plupart des explications sautent directement à l’implémentation et laissent l’invariant implicite — ce qui signifie que, dès qu’un interviewer demande « pourquoi cela fonctionne-t-il ? », il n’y a rien à dire.
L’invariant est la réponse : une fenêtre est valide lorsque chaque caractère requis apparaît au moins autant de fois que `t` l’exige. Tout le reste — les cartes de fréquences, le compteur `matched`, la boucle expansion puis rétrécissement — découle directement du suivi précis de cette condition. Une fois que vous maîtrisez l’invariant, le code suit. Une fois que vous pouvez énoncer l’invariant à voix haute, l’explication suit.
Avant votre prochain entretien, faites deux choses : répétez l’explication de 60 secondes de la section 6 jusqu’à ce qu’elle ressemble à une pensée et non à une récitation, puis déroulez ADOBECODEBANC à la main jusqu’à pouvoir annoncer l’état de `matched` à chaque étape sans regarder. Ces deux exercices amélioreront votre performance sous pression bien plus que n’importe quelle relecture supplémentaire.
Verve AI
Archives