Longest Palindrome

Q: Wie hoch ist die Zeitkomplexität von Longest Palindrome?

O(n) -Laufzeit beim Zählen: Jeder Buchstabe erhöht einen Zähler um 1, und beim Addieren der Paare werden unabhängig von der Länge von s 128 Zähler ausgelesen. Der Speicherbedarf beträgt O(1) . Sortieren und das Paaren benachbarter Elemente benötigen eine Laufzeit von O(n log n) und einen Speicherbedarf von O(n) .

LeichtHashing Greedy

+10

Du erhältst eine Zeichenfolge s aus Groß- und Kleinbuchstaben. Ordne ihre Buchstaben neu an, um das längste mögliche Palindrom zu bilden, und gib die Länge dieses Palindroms zurück. Du kannst die Buchstaben beliebig anordnen und einige weglassen, aber jeden Buchstaben höchstens so oft verwenden, wie er in s vorkommt.

Groß- und Kleinbuchstaben sind unterschiedliche Buchstaben, daher ist Aa kein Palindrom.

Funktion

longestPalindrome(s: string) → integer

sstring: die Buchstaben, die du verwenden darfst, in Groß- und Kleinschreibung
Gibt zurückinteger: die Länge des längsten Palindroms, das du aus diesen Buchstaben bilden kannst

Einschränkungen

1 ≤ s.length ≤ 5 × 10⁴
s enthält nur englische Buchstaben, a bis z und A bis Z.
Du musst nicht jeden Buchstaben verwenden.

Beispiele

Eingabe: s = "coddyCode"
Ausgabe: 5
Erklärung: o kommt zweimal vor und d dreimal, die übrigen jeweils einmal. Ein Paar os, ein Paar ds und ein übrig gebliebener Buchstabe in der Mitte ergeben die Länge 5, zum Beispiel doCod.

Eingabe: s = "Aa"
Ausgabe: 1
Erklärung: A und a sind unterschiedliche Buchstaben, daher gibt es kein Paar. Ein einzelner Buchstabe ist ein Palindrom der Länge 1.

Eingabe: s = "xxxyyy"
Ausgabe: 5
Erklärung: Zwei x und zwei y bilden Paare, und ein übrig gebliebener Buchstabe kommt in die Mitte, wie bei xyxyx. Das letzte y hat keinen Partner und bleibt draußen.

Weiterführende Frage

Kannst du auch ein längstes Palindrom selbst zusammen mit seiner Länge weiterhin in O(n)-Zeit zurückgeben?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Da du die Buchstaben umordnen darfst, spielt die Reihenfolge von s keine Rolle, sondern nur, wie oft jeder Buchstabe vorkommt. In einem Palindrom hat jeder Buchstabe auf der anderen Seite ein spiegelbildliches Gegenstück, mit Ausnahme von höchstens einem Buchstaben in der Mitte. Zähle also die Buchstaben, behalte jedes Paar und füge einen mittleren Buchstaben hinzu, falls ein Buchstabe übrig bleibt.

Nachbarn sortieren und paaren

Idee

Beim Sortieren werden gleiche Buchstaben nebeneinander angeordnet, sodass jedes Paar direkt nebeneinandersteht. In xxxyyy stimmen die x an den Indizes 0 und 1 überein: Nimm das Paar und gehe zwei Stellen weiter. Am Index 2 unterscheiden sich x und y, also bleibt dieses x ungepaart und du gehst eine Stelle weiter. Die y an den Indizes 3 und 4 bilden ein zweites Paar, und das letzte y bleibt allein. Zwei Paare ergeben 4, plus ein Buchstabe in der Mitte: 5.

Ein Buchstabe bleibt genau dann übrig, wenn die verwendeten Paare weniger als alle n Buchstaben umfassen, sodass du kein separates Flag benötigst. Das Sortieren benötigt O(n log n) Zeit, und die sortierte Kopie benötigt O(n) Speicherplatz.

Algorithmus

Sortiere die Buchstaben von s.
Gehe die sortierten Buchstaben mit einem Index i durch. Wenn die Buchstaben an den Positionen i und i+1 gleich sind, addiere 2 zur Länge und gehe zwei Positionen weiter; andernfalls gehe eine Position weiter.
Wenn die Länge kleiner als die Anzahl der Buchstaben ist, addiere 1 für den mittleren Buchstaben.
Gib die Länge zurück.

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

Zähle jeden Buchstaben

Idee

Zählen liefert dieselben Informationen, ohne zu sortieren. Verwende für jeden Zeichencode einen Zähler, insgesamt 128, damit A und a in unterschiedlichen Zählern landen. Ein Buchstabe, der c-mal vorkommt, liefert c, abgerundet auf eine gerade Anzahl von Buchstaben.

Bei coddyCode ergeben die Paare aus o und d 4 Buchstaben. Fünf Buchstaben bleiben übrig, und jeder davon kann in der Mitte stehen: 5. Ein zweiter ungepaarter Buchstabe hätte kein Spiegelbild.

Ein Durchlauf über s füllt die Zähler, und ein Durchlauf über die 128 Zähler addiert die Paare: Laufzeit O(n) und zusätzlicher Speicherplatz O(1) (O(n) in R, da s zunächst in einen Vektor aus Codes umgewandelt wird).

Algorithmus

Erstelle 128 Zähler, die auf 0 gesetzt sind, und addiere 1 zum Zähler jedes Buchstabens von s.
Addiere für jeden Zähler den auf eine gerade Zahl abgerundeten Wert zur Länge.
Wenn die Länge kleiner als die Länge von s ist, ist ein Zähler ungerade, also addiere 1 für den mittleren Buchstaben.
Gib die Länge zurück.

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

Stolperfallen und Grenzfälle

Ungerade Anzahlen vollständig zu verwerfen. Ein Buchstabe, der 3-mal vorkommt, liefert trotzdem ein Paar: xxxyyy ergibt 5, nicht 1.
Für jede ungerade Anzahl 1 hinzuzufügen. Nur ein Buchstabe passt in die Mitte, daher ergibt xxxyyy 5, nicht 6.
A und a als denselben Buchstaben zu behandeln. Aa enthält kein Paar, daher ist die Antwort 1, nicht 2.
Die Zähler nur für a bis z zu dimensionieren. Großbuchstaben haben die Zeichencodes 65 bis 90 und liegen außerhalb dieses Bereichs; verwende den vollständigen Zeichencode als Index.

Häufige Fragen3

Worin unterscheidet sich Longest Palindrome von Longest Palindromic Substring?

Hier kannst du die Buchstaben umordnen, daher zählen nur die Häufigkeiten, und das Zählen löst das Problem in O(n). Longest Palindromic Substring fragt nach einem Palindrom, das bereits als zusammenhängende Folge von Buchstaben vorkommt, und erfordert eine andere Methode, zum Beispiel die Ausdehnung um jedes Zentrum. Für abab lautet die Antwort bei diesem Problem 4 (abba), bei der Teilzeichenfolgen-Version 3 (aba).

Wie hoch ist die Zeitkomplexität von Longest Palindrome?

O(n)-Laufzeit beim Zählen: Jeder Buchstabe erhöht einen Zähler um 1, und beim Addieren der Paare werden unabhängig von der Länge von s 128 Zähler ausgelesen. Der Speicherbedarf beträgt O(1). Sortieren und das Paaren benachbarter Elemente benötigen eine Laufzeit von O(n log n) und einen Speicherbedarf von O(n).

Musst du jeden Buchstaben von s verwenden?

Nein. Jedes Paar kommt hinein, und höchstens ein ungepaartes Zeichen kommt in die Mitte. Die Antwort ist also die Länge von s, wenn höchstens ein Zeichen eine ungerade Anzahl hat, andernfalls die Länge von s minus der Anzahl der Zeichen mit einer ungeraden Anzahl plus 1.

def longestPalindrome(s):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

s = "coddyCode"

Erwartete Ausgabe