Longest Repeating Character Replacement

+10

On vous donne une chaîne s composée de lettres majuscules anglaises et 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, une suite de lettres consécutives, qui contient 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 de lettres identiques que vous pouvez former

Contraintes

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

Exemples

Entrée: s = "BAAACAB"k = 1
Sortie: 5
Explication: Remplacer le C par A fait que les indices de 1 à 5 affichent AAAAA. Les deux fenêtres de six lettres contiennent un B et le C, donc elles nécessitent deux modifications.

Entrée: s = "AABBBAB"k = 2
Sortie: 6
Explication: Les indices 1 à 6 contiennent ABBBAB, et remplacer les deux lettres A donne BBBBBB. La chaîne entière ne contient que quatre lettres B sur sept, elle nécessite donc trois modifications.

Pour aller plus loin

Qu'est-ce qui change si s peut contenir n'importe quel caractère au lieu des 26 lettres majuscules ?

Indices

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

0 sur 3 ouverts

Solution

Conservez la lettre la plus fréquente d’une sous-chaîne et remplacez les autres : une sous-chaîne de longueur len dont la lettre la plus fréquente apparaît top fois nécessite len - top remplacements. Une fenêtre glissante permet de trouver en un seul parcours la plus longue sous-chaîne telle que len - top ≤ k, car la fenêtre n’a jamais besoin de rétrécir et top n’a jamais besoin de diminuer.

Vérifie chaque sous-chaîne

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Pour chaque début, avancez la fin lettre par lettre, mettez à jour un compte pour chaque lettre et top, puis vérifiez len - top ≤ k. Chaque nouvelle sous-chaîne nécessite une seule mise à jour au lieu d’un nouveau comptage, et toutes les sous-chaînes sont vérifiées : la plus longue qui respecte la condition ne peut donc pas être manquée.

Une chaîne de longueur n contient environ n²/2 sous-chaînes : 1.25 × 10^9 vérifications pour n = 5 × 10^4.

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 désormais le plus élevé.
Si end - start + 1 - top ≤ k, enregistre la longueur si elle dépasse best.
Retourne 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

Choisis d’abord la lettre finale. Si la séquence finit par être composée uniquement de A, tu veux la plus longue sous-chaîne contenant au plus k lettres qui ne sont pas A.

Déplace right le long de la chaîne et compte les lettres qui ne sont pas la lettre cible dans la fenêtre. Lorsque le compte dépasse k, avance left jusqu’à ce qu’il revienne à k. Une fenêtre trop coûteuse le reste lorsqu’elle s’agrandit : left ne recule donc jamais, et pour chaque right, la fenêtre est la plus longue fenêtre valide qui se termine à cet endroit.

Effectue cette opération pour les 26 lettres et conserve le meilleur résultat : 26 parcours linéaires sur jusqu’à 5 × 10^4 lettres. La complexité reste O(n) uniquement 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 dans la chaîne. Si s[right] n’est pas la lettre cible, ajoute un à others.
Tant que others > k, avance left, en soustrayant un lorsque la lettre qui quitte la fenêtre n’est pas la lettre cible.
Enregistre right - left + 1 si cette valeur est supérieure à best.
Après 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

Gardez 26 compteurs pour la fenêtre et top, le compteur le plus élevé. Lorsque l’ajout de s[right] rend la fenêtre trop coûteuse, retirez une lettre à gauche : la fenêtre se décale et conserve sa longueur, car seule une fenêtre plus longue peut battre le record. Sinon, elle s’agrandit d’une unité. Sa longueur est toujours la meilleure obtenue jusque-là, donc la réponse est n - left.

Lorsqu’une lettre sort de la fenêtre, ne modifiez pas top, même s’il est désormais supérieur au compteur réel. Après un décalage, la longueur est exactement top + k. Pour s’agrandir, il faut donc qu’une lettre apparaisse top + 1 fois, et top augmente alors en conséquence. Un top obsolète ne peut que faire décaler la fenêtre, et un décalage ne peut pas faire perdre le record.

Dans BAAACAB avec k = 1, BAAAC nécessite 2 modifications et la fenêtre se décale pour devenir AAAC. Le A suivant fait passer top à 4 et la fenêtre s’agrandit pour devenir AAACA, d’une longueur de 5.

Algorithme

Maintenez les comptages des 26 lettres, left = 0 et top = 0.
Déplacez right dans la chaîne : ajoutez s[right] à son comptage et augmentez top si ce comptage est maintenant supérieur.
Si right - left + 1 - top > k, retirez s[left] des comptages et déplacez left d’un pas. Ne diminuez jamais top.
Retournez 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

Ajouter k à la séquence la plus longue. Dans AAAB avec k = 3, cela donne 6, plus long que la chaîne. Dans BAAACAB avec k = 1, cela donne 4, mais remplacer le C relie deux séquences et en forme une de 5.
Compter les changements par rapport à la première lettre de la fenêtre au lieu de sa lettre la plus fréquente. BAAA nécessite un changement, et non trois.
Renvoyer n - left depuis une boucle qui réduit la fenêtre avec while et recalcule le maximum réel. Cette fenêtre rétrécit, donc conserve un best distinct.
Mesurer la fenêtre comme right - left. Ses deux extrémités en font partie, donc ajoute un.

Questions fréquentes3

Quelle est la complexité temporelle de Longest Repeating Character Replacement ?

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

En quoi est-ce différent de « Longest Substring Without Repeating Characters » ?

Les deux déplacent deux bords sur la chaîne, mais la règle définissant une fenêtre valide diffère. Là-bas, aucun caractère ne peut se répéter, donc la fenêtre rétrécit jusqu’à ce que la répétition disparaisse. Ici, la longueur moins le nombre maximal doit être inférieur ou égal à k, donc la fenêtre peut glisser en gardant une longueur fixe.

Ce problème peut-il être résolu par recherche binaire ?

Oui. Si une sous-chaîne de longueur L est accessible, toutes les sous-chaînes plus courtes qu’elle contient le sont aussi, donc tu peux effectuer une recherche binaire sur L. Pour chaque L, fais glisser une fenêtre fixe de cette longueur et vérifie si une position nécessite au plus k modifications. Cela donne une complexité de O(n log n), plus lente que la solution à une seule fenêtre.

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

Test #1

Test #2

Test #3

Arguments

s = "BAAACAB"
k = 1

Résultat attendu

Longest Repeating Character Replacement

Fonction

Contraintes

Exemples

Indices

Solution

Vérifie 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équentes3

Problèmes similaires