Longest Palindrome

Q: Jaka jest złożoność czasowa problemu najdłuższego palindromu?

Czas O(n) przy zliczaniu: każda litera dodaje 1 do jednego licznika, a sumowanie par wymaga odczytania 128 liczników niezależnie od długości s . Złożoność pamięciowa wynosi O(1) . Sortowanie i łączenie sąsiednich elementów kosztuje O(n log n) czasu i O(n) pamięci.

ŁatweHaszowanie Algorytmy zachłanne

+10

Otrzymujesz ciąg znaków s złożony z wielkich i małych liter. Ułóż jego litery tak, aby utworzyć jak najdłuższy palindrom, i zwróć jego długość. Możesz ułożyć litery w dowolnej kolejności i pominąć niektóre z nich, ale każdej litery możesz użyć najwyżej tyle razy, ile występuje w s.

Wielkie i małe litery są różnymi literami, więc Aa nie jest palindromem.

Funkcja

longestPalindrome(s: string) → integer

sstring: litery, których możesz używać, wielkie i małe
Zwracainteger: długość najdłuższego palindromu, jaki możesz ułożyć z tych liter

Ograniczenia

1 ≤ s.length ≤ 5 × 10⁴
s zawiera tylko angielskie litery: a–z oraz A–Z.
Nie musisz używać każdej litery.

Przykłady

Wejście: s = "coddyCode"
Wyjście: 5
Wyjaśnienie: o występuje dwa razy, a d trzy razy, pozostałe litery po razie. Para liter o, para liter d i jedna pozostała litera w środku dają długość 5, na przykład doCod.

Wejście: s = "Aa"
Wyjście: 1
Wyjaśnienie: A i a to różne litery, więc taka para nie istnieje. Pojedyncza litera sama w sobie jest palindromem o długości 1.

Wejście: s = "xxxyyy"
Wyjście: 5
Wyjaśnienie: Dwie litery x i dwie litery y tworzą pary, a jedna pozostała litera trafia na środek, jak w xyxyx. Ostatnia litera y nie ma pary i pozostaje poza nimi.

Pytanie dodatkowe

Czy możesz zwrócić jeden z najdłuższych palindromów wraz z jego długością, nadal w czasie O(n)?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Ponieważ możesz przestawiać litery, kolejność s nie ma znaczenia, liczy się tylko to, ile razy występuje każda litera. W palindromie każda litera ma lustrzaną kopię po drugiej stronie, z wyjątkiem co najwyżej jednej litery na środku. Policz więc litery, zachowaj każdą parę i dodaj jedną literę na środek, jeśli jakaś litera zostanie.

Sortuj i łącz sąsiadów

Intuicja

Sortowanie umieszcza takie same litery obok siebie, więc każda para znajduje się obok siebie. W xxxyyy litery x na pozycjach 0 i 1 pasują do siebie: utwórz parę i przesuń się o dwie pozycje. Na indeksie 2 litery x i y różnią się, więc ta litera x pozostaje bez pary i przesuwasz się o jedną pozycję. Litery y na pozycjach 3 i 4 tworzą drugą parę, a ostatnia litera y pozostaje sama. Dwie pary dają 4, plus jedna środkowa litera: 5.

Litera pozostaje niewykorzystana dokładnie wtedy, gdy pary obejmują mniej niż wszystkie n litery, więc nie potrzebujesz osobnej flagi. Sortowanie zajmuje O(n log n) czasu, a posortowana kopia zajmuje O(n) pamięci.

Algorytm

Posortuj litery w s.
Przejdź przez posortowane litery, używając indeksu i. Jeśli litery na pozycjach i i i+1 są takie same, dodaj 2 do długości i przesuń się o dwie pozycje; w przeciwnym razie przesuń się o jedną pozycję.
Jeśli długość jest mniejsza niż liczba liter, dodaj 1 za środkową literę.
Zwróć długość.

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

Policz każdą literę

Intuicja

Zliczanie dostarcza tych samych informacji bez sortowania. Utrzymuj jeden licznik dla każdego kodu znaku — 128 liczników — dzięki czemu A i a trafią do różnych liczników. Litera występująca c razy dostarcza c zaokrąglone w dół do parzystej liczby liter.

Dla coddyCode pary liter o i d dają 4 litery. Zostaje pięć liter, z których dowolna może znaleźć się w środku: 5. Druga niesparowana litera nie miałaby swojego odbicia.

Jedno przejście po s wypełnia liczniki, a jedno przejście po 128 licznikach sumuje pary: czas O(n) i dodatkowa pamięć O(1) (O(n) w R, gdzie s jest najpierw konwertowane na wektor kodów).

Algorytm

Utwórz 128 liczników ustawionych na 0 i dodaj 1 do licznika każdej litery z s.
Dla każdego licznika dodaj do długości jego wartość zaokrągloną w dół do liczby parzystej.
Jeśli długość jest mniejsza niż długość s, któryś licznik jest nieparzysty, więc dodaj 1 za środkową literę.
Zwróć długość.

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

Pułapki i przypadki brzegowe

Całkowite pomijanie nieparzystych liczności. Litera, która występuje 3 razy, nadal dostarcza jedną parę: xxxyyy daje 5, a nie 1.
Dodawanie 1 za każdą nieparzystą liczność. Tylko jedna litera może znaleźć się w środku, więc xxxyyy daje 5, a nie 6.
Traktowanie A i a jako tej samej litery. Aa nie zawiera żadnej pary, więc odpowiedź to 1, a nie 2.
Przydzielanie licznikom rozmiaru obejmującego tylko litery od a do z. Wielkie litery mają kody od 65 do 90 i wypadają poza ten zakres; indeksuj według pełnego kodu znaku.

Najczęstsze pytania3

Czym różni się najdłuższy palindrom od najdłuższego podciągu palindromicznego?

Tutaj możesz przestawiać litery, więc liczą się tylko ich liczby i zliczanie rozwiązuje problem w czasie O(n). Problem Najdłuższego Palindromu w Podciągu wymaga znalezienia palindromu, który już występuje jako blok kolejnych liter, i wymaga innej metody, na przykład rozszerzania wokół każdego środka. Dla abab odpowiedzią w tym problemie jest 4 (abba), a w wersji dotyczącej podciągu — 3 (aba).

Jaka jest złożoność czasowa problemu najdłuższego palindromu?

Czas O(n) przy zliczaniu: każda litera dodaje 1 do jednego licznika, a sumowanie par wymaga odczytania 128 liczników niezależnie od długości s. Złożoność pamięciowa wynosi O(1). Sortowanie i łączenie sąsiednich elementów kosztuje O(n log n) czasu i O(n) pamięci.

Czy musisz użyć każdej litery z s?

Nie. Każda para zostaje wykorzystana, a na środku może znaleźć się najwyżej jedna niesparowana litera. Zatem odpowiedzią jest długość s, jeśli co najwyżej jedna litera występuje nieparzystą liczbę razy, a w przeciwnym razie długość s pomniejszona o liczbę liter występujących nieparzystą liczbę razy, plus 1.

def longestPalindrome(s):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argument

s = "coddyCode"

Oczekiwany wynik