Longest Palindrome

Q: Quelle est la complexité temporelle de Longest Palindrome ?

Un temps de O(n) avec le comptage : chaque lettre ajoute 1 à un compteur, et additionner les paires lit 128 compteurs quelle que soit la longueur de s . L’espace utilisé est de O(1) . Le tri et l’appariement des voisins coûtent O(n log n) en temps et O(n) en espace.

FacileHachage Glouton

+10

Vous recevez une chaîne s composée de lettres majuscules et minuscules. Réorganisez ses lettres pour former le plus long palindrome possible et renvoyez la longueur de ce palindrome. Vous pouvez placer les lettres dans n’importe quel ordre et en laisser certaines de côté, mais vous ne pouvez utiliser chaque lettre qu’au plus autant de fois qu’elle apparaît dans s.

Les majuscules et les minuscules sont des lettres différentes, donc Aa n’est pas un palindrome.

Fonction

longestPalindrome(s: string) → integer

sstring: les lettres que vous pouvez utiliser, en majuscules et en minuscules
Renvoieinteger: la longueur du plus long palindrome que tu peux construire avec ces lettres

Contraintes

1 ≤ s.length ≤ 5 × 10⁴
s contient uniquement des lettres anglaises, de a à z et de A à Z.
Tu n’as pas besoin d’utiliser toutes les lettres.

Exemples

Entrée: s = "coddyCode"
Sortie: 5
Explication: o apparaît deux fois et d trois fois, les autres une fois. Une paire de o, une paire de d et une lettre restante au milieu donnent une longueur de 5, par exemple doCod.

Entrée: s = "Aa"
Sortie: 1
Explication: A et a sont des lettres différentes, donc aucune paire n’existe. Une lettre seule est un palindrome de longueur 1.

Entrée: s = "xxxyyy"
Sortie: 5
Explication: Deux x et deux y forment des paires, et une lettre restante va au milieu, comme dans xyxyx. Le dernier y n’a pas de partenaire et reste à l’écart.

Pour aller plus loin

Pouvez-vous renvoyer le palindrome lui-même, le plus long, ainsi que sa longueur, toujours en temps O(n) ?

Indices

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

0 sur 3 ouverts

Solution

Comme tu peux réarranger les lettres, l’ordre de s n’a pas d’importance, seul compte le nombre d’occurrences de chaque lettre. Dans un palindrome, chaque lettre a une copie en miroir de l’autre côté, à l’exception d’au plus une lettre au milieu. Compte donc les lettres, garde chaque paire et ajoute une lettre au milieu s’il en reste une.

Trier et associer les voisins

Intuition

Le tri place les lettres identiques les unes à côté des autres, de sorte que chaque paire est côte à côte. Dans xxxyyy, les x aux indices 0 et 1 correspondent : prends la paire et avance de deux places. À l’indice 2, x et y sont différents, donc ce x reste sans paire et tu avances d’une place. Les y aux indices 3 et 4 forment une deuxième paire, et le dernier y est seul. Deux paires donnent 4, plus une lettre au milieu : 5.

Il reste une lettre exactement lorsque les paires utilisent moins de n lettres au total, donc tu n’as pas besoin d’un indicateur distinct. Le tri prend un temps de O(n log n), et la copie triée occupe un espace de O(n).

Algorithme

Trie les lettres de s.
Parcours les lettres triées avec un indice i. Si les lettres aux positions i et i+1 sont égales, ajoute 2 à la longueur et avance de deux positions ; sinon, avance d’une position.
Si la longueur est inférieure au nombre de lettres, ajoute 1 pour la lettre du milieu.
Renvoie la longueur.

def longestPalindrome(s):
    letters = sorted(s)
    n = len(letters)
    length = 0
    i = 0
    while i + 1 < n:
        if letters[i] == letters[i + 1]:
            length += 2  # a pair: one copy on each side of the middle
            i += 2
        else:
            i += 1
    # A letter left without a partner can stand alone in the middle
    if length < n:
        length += 1
    return length

Compter chaque lettre

Intuition

Le comptage fournit les mêmes informations sans tri. Gardez un compteur par code de caractère, soit 128 compteurs, afin que A et a soient comptabilisés séparément. Une lettre qui apparaît c fois fournit c arrondi à l’entier pair inférieur en nombre de lettres.

Pour coddyCode, les paires de o et de d donnent 4 lettres. Cinq lettres sont laissées de côté, et n’importe laquelle d’entre elles peut occuper le milieu : 5. Une deuxième lettre sans paire n’aurait pas de miroir.

Un parcours de s remplit les compteurs et un parcours des 128 compteurs additionne les paires : temps O(n) et espace supplémentaire O(1) (O(n) en R, qui convertit d’abord s en un vecteur de codes).

Algorithme

Créez 128 compteurs initialisés à 0, puis ajoutez 1 au compteur de chaque lettre de s.
Pour chaque compteur, ajoutez à la longueur le nombre arrondi à l'entier pair inférieur.
Si la longueur est inférieure à la longueur de s, certains nombres sont impairs : ajoutez donc 1 pour la lettre du milieu.
Renvoyez la longueur.

def longestPalindrome(s):
    counts = [0] * 128  # one counter per character code, so 'A' and 'a' differ
    for ch in s:
        counts[ord(ch)] += 1
    length = 0
    for count in counts:
        length += count // 2 * 2  # every pair fits, one copy on each side
    # Fewer letters used than s has: some count is odd, so one letter can go in the middle
    if length < len(s):
        length += 1
    return length

Pièges et cas limites

Ignorer complètement les nombres impairs. Une lettre qui apparaît 3 fois fournit tout de même une paire : xxxyyy donne 5, et non 1.
Ajouter 1 pour chaque nombre impair. Une seule lettre peut se trouver au milieu, donc xxxyyy donne 5, et non 6.
Considérer A et a comme la même lettre. Aa ne contient aucune paire, donc la réponse est 1, et non 2.
Dimensionner les compteurs uniquement de a à z. Les lettres majuscules ont des codes de 65 à 90 et se trouvent en dehors de cette plage ; utiliser le code complet du caractère comme index.

Questions fréquentes3

Quelle est la différence entre le plus long palindrome et la plus longue sous-chaîne palindromique ?

Ici, tu peux réarranger les lettres : seuls les décomptes comptent, et les compter suffit à résoudre le problème en O(n). Le problème de la sous-chaîne palindromique la plus longue consiste à trouver un palindrome qui apparaît déjà sous la forme d’un bloc de lettres consécutives, et nécessite une autre méthode, comme l’expansion autour de chaque centre. Pour abab, ce problème renvoie 4 (abba), tandis que la version sous-chaîne renvoie 3 (aba).

Quelle est la complexité temporelle de Longest Palindrome ?

Un temps de O(n) avec le comptage : chaque lettre ajoute 1 à un compteur, et additionner les paires lit 128 compteurs quelle que soit la longueur de s. L’espace utilisé est de O(1). Le tri et l’appariement des voisins coûtent O(n log n) en temps et O(n) en espace.

Faut-il utiliser toutes les lettres de s ?

Non. Chaque paire est incluse, et au plus une lettre non appariée est placée au milieu. La réponse est donc la longueur de s s’il y a au plus une lettre dont le nombre d’occurrences est impair, et sinon la longueur de s moins le nombre de lettres dont le nombre d’occurrences est impair, plus 1.

def longestPalindrome(s):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

s = "coddyCode"

Résultat attendu