Longest Repeating Character Replacement

+10

Vous disposez d’une chaîne s composée de lettres majuscules anglaises et d’un entier k. Vous pouvez choisir au plus k positions de s et remplacer la lettre à chacune de ces positions par n’importe quelle autre lettre majuscule.

Renvoyez la longueur de la plus longue sous-chaîne, c’est-à-dire une suite de lettres adjacentes, qui ne contient qu’une seule lettre répétée après vos modifications.

Fonction

characterReplacement(s: string, k: integer) → integer

sstring: la chaîne de lettres majuscules
kinteger: le plus grand nombre de lettres que vous pouvez modifier
Renvoieinteger: la longueur de la plus longue sous-chaîne composée d’une même lettre répétée que vous pouvez obtenir

Contraintes

1 ≤ s.length ≤ 5 × 10⁴
s contient uniquement des lettres majuscules anglaises.
0 ≤ k ≤ s.length

Exemples

Entrée: s = "BAAACAB"k = 1
Sortie: 5
Explication: Remplacez le C par un A et les indices de 1 à 5 donnent AAAAA. Six lettres nécessiteraient deux changements : les indices de 0 à 5 contiennent un B et le C, et les indices de 1 à 6 contiennent le C et le dernier B.

Entrée: s = "AABBBAB"k = 2
Sortie: 6
Explication: Dans ABBBAB, aux indices 1 à 6, les deux A sont les seules lettres qui ne sont pas B, donc deux changements donnent BBBBBB. La chaîne entière contient trois A et quatre B, donc elle nécessite trois changements.

+17 tests cachés à la soumission

Pour aller plus loin

Qu’est-ce qui change si s peut contenir n’importe quel caractère, et pas seulement les 26 lettres majuscules ?

Indices

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

0 sur 3 ouverts

Solution

Le coût d’une sous-chaîne est facile à voir : sa longueur moins le nombre d’occurrences de sa lettre la plus fréquente. La difficulté est de ne pas avoir à payer pour les n² sous-chaînes. Une fenêtre glissante parcourt la chaîne une seule fois, et la meilleure version repose sur deux faits : la fenêtre n’a jamais besoin de rétrécir, et le nombre maximal d’occurrences d’une lettre n’a jamais besoin de diminuer.

Vérifiez chaque sous-chaîne

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Corrigez une sous-chaîne. Quelle lettre doit-elle devenir ? Celle qui apparaît déjà le plus souvent, car toutes les autres lettres doivent changer. Ainsi, une sous-chaîne de longueur len dont la lettre la plus fréquente apparaît top fois nécessite len - top changements, et elle est réalisable lorsque cette valeur est inférieure ou égale à k.

Essayez toutes les sous-chaînes. Pour chaque début, prolongez la fin d’une lettre à la fois et conservez un compte par lettre, en augmentant top au fur et à mesure. Chaque nouvelle sous-chaîne ne nécessite alors qu’une mise à jour au lieu d’un nouveau comptage. Toutes les sous-chaînes sont vérifiées, donc la plus longue sous-chaîne réalisable ne peut pas être manquée.

C’est lent, car une chaîne de longueur n contient environ n²/2 sous-chaînes. Pour n = 5 × 10^4, cela représente 1.25 × 10^9 vérifications, bien plus que ce que la limite de temps autorise.

Algorithme

Définis best à 0.
Pour chaque indice de départ, réinitialise les 26 compteurs et top à 0.
Déplace end du début jusqu’au dernier indice. Ajoute s[end] à son compteur, et augmente top si ce compteur est maintenant le plus élevé.
Si end - start + 1 - top ≤ k, la sous-chaîne est accessible : enregistre sa longueur si elle dépasse best.
Renvoie best.

def characterReplacement(s, k):
    n = len(s)
    best = 0
    for start in range(n):
        count = [0] * 26  # letters in s[start..end]
        top = 0           # count of the most common letter there
        for end in range(start, n):
            c = ord(s[end]) - ord('A')
            count[c] += 1
            top = max(top, count[c])
            # Every letter that is not the most common one must change.
            if end - start + 1 - top <= k:
                best = max(best, end - start + 1)
    return best

Une fenêtre glissante par lettre cible

Intuition

Inverse la question et choisis d’abord la lettre. Si la séquence finale est composée uniquement de A, la question devient : quelle est la plus longue sous-chaîne contenant au plus k lettres qui ne sont pas des A ? C’est un classique de la fenêtre glissante.

Parcours la chaîne avec right et compte les lettres de la fenêtre qui ne sont pas la cible. Lorsque ce nombre dépasse k, avance left jusqu’à ce qu’il revienne à k. Agrandir une fenêtre ne peut qu’ajouter des lettres à modifier : une fenêtre dont le coût est trop élevé le reste lorsqu’elle s’agrandit, et left n’a jamais besoin de reculer. Pour chaque right, la fenêtre conservée est la plus longue fenêtre valide qui se termine à cet endroit.

Effectue cette opération pour les 26 lettres et conserve la meilleure longueur. Chaque parcours prend O(n), soit 26 passages au total, environ 1.3 × 10^6 étapes pour n = 5 × 10^4. C’est linéaire, mais la chaîne est parcourue 26 fois, et cette méthode ne fonctionne que parce que l’alphabet est petit.

Algorithme

Pour chaque lettre cible de A à Z, commence une fenêtre avec left = 0 et others = 0.
Déplace right le long de la chaîne. Si s[right] n’est pas la lettre cible, ajoute 1 à others.
Tant que others > k, avance left et soustrais 1 de others lorsque la lettre qui sort n’est pas la lettre cible.
Enregistre right - left + 1 si cette valeur dépasse best.
Après avoir traité les 26 lettres, renvoie best.

def characterReplacement(s, k):
    best = 0
    for target in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
        left = 0
        others = 0  # letters in s[left..right] that are not target
        for right in range(len(s)):
            if s[right] != target:
                others += 1
            # Too many letters to change: drop letters from the left.
            while others > k:
                if s[left] != target:
                    others -= 1
                left += 1
            best = max(best, right - left + 1)
    return best

Une fenêtre qui ne rétrécit jamais

Intuition

Traitez chaque lettre dans une fenêtre. Comptez chacune des 26 lettres qui s’y trouvent, ainsi que top, le nombre le plus élevé. La fenêtre nécessite length - top modifications ; elle est donc valide si ce nombre est inférieur ou égal à k.

Premier fait : la fenêtre n’a jamais besoin de rétrécir. Vous cherchez seulement à dépasser la meilleure longueur trouvée jusqu’ici ; ainsi, lorsque l’ajout de s[right] rend la fenêtre trop coûteuse, retirez une lettre à gauche. La fenêtre se décale d’un cran et conserve sa longueur. Lorsque la fenêtre n’est pas trop coûteuse, elle s’agrandit d’une unité. Sa longueur correspond donc toujours à la meilleure longueur trouvée jusqu’ici et, à la fin, la réponse est n - left.

Deuxième fait : top n’a jamais besoin de diminuer. Lorsqu’une lettre quitte la fenêtre à gauche, vous ne modifiez pas top ; sa valeur peut donc être supérieure au nombre réel de lettres dans la fenêtre. Cela ne pose pas de problème. Après un décalage, la longueur de la fenêtre est exactement top + k ; pour l’agrandir, il faut donc une lettre présente top + 1 fois dans la fenêtre, et à ce moment-là, top augmente avec elle. Un top obsolète peut faire glisser la fenêtre, mais jamais l’agrandir par erreur ; et ce glissement ne fait perdre aucune possibilité, car seule une fenêtre plus longue pourrait battre le record.

Dans BAAACAB avec k = 1, la fenêtre s’agrandit jusqu’à BAAA, puis BAAAC nécessite 2 modifications ; elle glisse donc jusqu’à AAAC. L’ajout du A suivant fait passer top à 4 et la fenêtre s’agrandit jusqu’à AAACA, de longueur 5. Le dernier B la fait glisser une fois de plus ; la réponse est donc 5.

Algorithme

Conservez les compteurs des 26 lettres, left = 0 et top = 0.
Déplacez right sur la chaîne : ajoutez s[right] à son compteur et augmentez top si ce compteur est désormais plus élevé.
Si right - left + 1 - top > k, la fenêtre nécessite trop de modifications : retirez s[left] des compteurs et déplacez left d’un pas. La fenêtre glisse et conserve sa longueur.
Ne diminuez jamais top lorsqu’une lettre quitte la fenêtre.
Renvoyez la longueur finale de la fenêtre, n - left.

def characterReplacement(s, k):
    count = [0] * 26  # letters inside the window s[left..right]
    left = 0
    top = 0  # the highest count any letter has reached in a window
    for right in range(len(s)):
        c = ord(s[right]) - ord('A')
        count[c] += 1
        top = max(top, count[c])
        # Needs more than k changes: slide the window instead of growing it.
        if right - left + 1 - top > k:
            count[ord(s[left]) - ord('A')] -= 1
            left += 1
    # The window only grew when a longer valid substring was found.
    return len(s) - left

Pièges et cas limites

Le code de la fenêtre est court, donc la plupart des mauvaises réponses viennent de la formule du coût ou d’un raccourci qui semble correct à première vue.

Ajouter k à la plus longue séquence. Dans AAAB avec k = 3, cela donne 6, soit plus que la longueur de la chaîne. Dans BAAACAB avec k = 1, cela donne 4, mais le changement nécessaire se trouve au milieu et réunit deux séquences pour en former une de longueur 5.
Compter les changements par rapport à la première lettre de la fenêtre plutôt qu’à sa lettre la plus fréquente. La fenêtre BAAA nécessite un changement, pas trois.
Renvoyer n - left dans une version où la fenêtre peut rétrécir. Ce raccourci ne fonctionne que lorsque la fenêtre ne devient jamais plus petite, comme dans le code à fenêtre unique ici. Si ta boucle rétrécit la fenêtre avec while et recalcule le maximum réel, conserve un best séparé.
Mesurer la fenêtre avec right - left. Ses deux extrémités en font partie, il faut donc ajouter un.
Traiter k = 0 comme un cas particulier. Sans changement, la règle de la fenêtre renvoie déjà la plus longue séquence d’une seule lettre.

Questions fréquentes4

Quelle est la complexité temporelle de l’algorithme de remplacement du caractère répétitif le plus long ?

La solution à fenêtre unique s’exécute en O(n), où n est la longueur de s : right parcourt chaque lettre une fois et left avance au plus une fois par étape. Elle utilise un espace supplémentaire de O(1), avec 26 compteurs et quelques entiers.

Pourquoi la fréquence maximale n'a-t-elle pas besoin d'être mise à jour lorsque la fenêtre glisse ?

La fenêtre essaie seulement de battre son propre record. Après un déplacement, sa longueur est top + k, donc une fenêtre valide plus longue nécessite qu’une lettre apparaisse plus de top fois, ce qui augmente de toute façon top. Une valeur de top trop élevée ne fait que maintenir la fenêtre à sa longueur ; elle ne la fait jamais grandir alors qu’elle ne devrait pas.

En quoi cela diffère-t-il du problème de la plus longue sous-chaîne sans caractères répétés ?

Les deux parcourent la chaîne de deux côtés, mais la règle qui définit une fenêtre valide diffère. Là-bas, une fenêtre est valide lorsqu’aucun caractère ne se répète, et elle doit rétrécir jusqu’à ce que la répétition disparaisse. Ici, une fenêtre est valide lorsque sa longueur moins le nombre d’occurrences de sa lettre la plus fréquente est inférieur ou égal à k, ce qui permet à la fenêtre de glisser à longueur constante au lieu de rétrécir.

Ce problème peut-il être résolu à l’aide de la recherche dichotomique ?

Oui. Si une sous-chaîne de longueur L est atteignable, toutes les sous-chaînes plus courtes qu’elle contient le sont aussi, donc tu peux faire une recherche binaire sur L. Pour chaque L, fais glisser une fenêtre de longueur fixe et vérifie si une position nécessite au plus k changements. Cela donne O(n log n), ce qui est plus lent que la solution à une seule fenêtre, mais constitue une réponse tout à fait acceptable.

Python

def characterReplacement(s, k):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

s = "BAAACAB"
k = 1

Attendu

Longest Repeating Character Replacement

Fonction

Contraintes

Exemples

Indices

Solution

Vérifiez chaque sous-chaîne

Une fenêtre glissante par lettre cible

Une fenêtre qui ne rétrécit jamais

Pièges et cas limites

Questions fréquentes4

Problèmes similaires