Longest Palindrome

Q: En Uzun Palindromun zaman karmaşıklığı nedir?

Sayma ile O(n) zaman: her harf bir sayaca 1 ekler ve çiftleri toplamak, s 'nin uzunluğu ne olursa olsun 128 sayacı okur. Alan kullanımı O(1) 'dir. Sıralama ve komşuları eşleştirme işlemi O(n log n) zaman ve O(n) alan kullanır.

KolayHashing Açgözlü

+10

Büyük ve küçük harflerden oluşan bir s dizgesi alırsın. Harflerini yeniden sıralayarak oluşturabileceğin en uzun palindromu kur ve bu palindromun uzunluğunu döndür. Harfleri istediğin sırada kullanabilir ve bazılarını kullanmayabilirsin; ancak her harfi en fazla s içinde göründüğü sayıda kullanabilirsin.

Büyük ve küçük harfler farklı harflerdir; bu nedenle Aa bir palindrom değildir.

Fonksiyon

longestPalindrome(s: string) → integer

sstring: kullanabileceğiniz harfler; büyük ve küçük harfler
Döndürürinteger: bu harflerden oluşturabileceğiniz en uzun palindromun uzunluğu

Kısıtlar

1 ≤ s.length ≤ 5 × 10⁴
s yalnızca İngilizce harfler, a ile z ve A ile Z arasındaki harfleri içerir.
Her harfi kullanmak zorunda değilsiniz.

Örnekler

Girdi: s = "coddyCode"
Çıktı: 5
Açıklama: o iki kez, d üç kez, geri kalanlar ise birer kez görünür. Bir çift o, bir çift d ve ortada kalan bir harf uzunluğu 5 yapar; örneğin doCod.

Girdi: s = "Aa"
Çıktı: 1
Açıklama: A ve a farklı harflerdir, bu yüzden eşleşen bir çift yoktur. Tek başına duran tek bir harf, uzunluğu 1 olan bir palindromdur.

Girdi: s = "xxxyyy"
Çıktı: 5
Açıklama: İki x ve iki y eşleşmeler oluşturur ve xyxyx örneğindeki gibi, artan bir harf ortaya yerleşir. Son y eşleşecek bir harf bulamaz ve dışarıda kalır.

Ek soru

En uzun palindromun kendisini uzunluğuyla birlikte, yine O(n) zamanda döndürebilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Yeniden düzenleyebileceğin için s harflerinin sırası önemli değildir; yalnızca her harfin kaç kez geçtiği önemlidir. Bir palindromda, ortadaki en fazla bir harf dışında her harfin diğer tarafta ayna görüntüsü vardır. Bu yüzden harfleri say, her çifti koru ve geriye harf kalırsa ortada kullanmak üzere bir harf ekle.

Komşuları sırala ve eşleştir

Sezgi

Sıralama, aynı harfleri yan yana getirir; böylece her çift yan yana durur. xxxyyy içinde, 0 ve 1 indekslerindeki x harfleri eşleşir: çifti al ve iki yer ilerle. 2. indekste x ve y farklıdır, bu yüzden o x eşleşmeden kalır ve bir yer ilerlersin. 3 ve 4 indekslerindeki y harfleri ikinci bir çift oluşturur ve son y tek kalır. İki çift 4 eder, buna ortadaki bir harfi ekle: 5.

Bir harf, çiftler n harfin tamamından daha azını kullandığında artar; bu yüzden ayrı bir bayrağa gerek yoktur. Sıralama O(n log n) zaman alır ve sıralanmış kopya O(n) alan kullanır.

Algoritma

s harflerini sırala.
Sıralanmış harfler üzerinde i indeksiyle ilerle. i ve i+1 konumlarındaki harfler eşitse uzunluğa 2 ekle ve iki konum ilerle; aksi takdirde bir konum ilerle.
Uzunluk harf sayısından azsa ortadaki harf için 1 ekle.
Uzunluğu döndür.

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

Her harfi say

Sezgi

Sayma, sıralama yapmadan aynı bilgiyi verir. Her karakter kodu için bir sayaç tut; toplam 128 sayaç olsun. Böylece A ve a farklı sayaçlara düşer. c kez görünen bir harf, çift sayıya aşağı yuvarlanmış c kadar harf sağlar.

coddyCode için o ve d çiftleri 4 harf verir. Beş harf dışarıda kalır ve bunlardan herhangi biri ortada yer alabilir: 5. Eşleşmeyen ikinci bir harfin aynadaki karşılığı olmaz.

s üzerinde bir geçiş sayaçları doldurur, 128 sayaç üzerinde bir geçiş de çiftleri toplar: O(n) zaman ve O(1) ek alan (s'yi önce kodlardan oluşan bir vektöre dönüştürdüğü için R'de O(n)).

Algoritma

0 olarak ayarlanmış 128 sayaç oluştur ve s içindeki her harfin sayacına 1 ekle.
Her sayaç için, aşağı yuvarlanarak elde edilen çift sayıyı uzunluğa ekle.
Uzunluk s uzunluğundan küçükse, bazı sayımlar tektir; bu nedenle ortadaki harf için 1 ekle.
Uzunluğu döndür.

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

Tuzaklar ve uç durumlar

Tek sayıları tamamen yok saymak. 3 kez görünen bir harf yine de bir çift sağlar: xxxyyy 1 değil, 5 sonucunu verir.
Her tek sayı için 1 eklemek. Ortada yalnızca bir harf bulunabilir, bu nedenle xxxyyy 6 değil, 5 sonucunu verir.
A ve a harflerini aynı harf olarak kabul etmek. Aa içinde hiç çift yoktur, bu nedenle yanıt 2 değil, 1'dir.
Sayaçları yalnızca a ile z arasındaki harfler için boyutlandırmak. Büyük harflerin kodları 65 ile 90 arasındadır ve bu aralığın dışında kalırlar; dizini karakter kodunun tamamına göre belirleyin.

Sıkça sorulan sorular3

En Uzun Palindrom ile En Uzun Palindromik Alt Dize arasındaki fark nedir?

Burada harfleri yeniden sıralayabilirsin; bu yüzden yalnızca sayılar önemlidir ve sayma işlemi bunu O(n) sürede çözer. Longest Palindromic Substring, art arda gelen harflerden oluşan bir blok olarak zaten bulunan bir palindrom ister ve her merkezin çevresini genişletmek gibi başka bir yöntem gerektirir. abab için bu problem 4 (abba), alt dize sürümü ise 3 (aba) yanıtını verir.

En Uzun Palindromun zaman karmaşıklığı nedir?

Sayma ile O(n) zaman: her harf bir sayaca 1 ekler ve çiftleri toplamak, s'nin uzunluğu ne olursa olsun 128 sayacı okur. Alan kullanımı O(1)'dir. Sıralama ve komşuları eşleştirme işlemi O(n log n) zaman ve O(n) alan kullanır.

s'nin her harfini kullanmak zorunda mısın?

Hayır. Her çift içeri girer ve ortada eşleşmemiş en fazla bir harf bulunur. Bu nedenle, en fazla bir harfin sayısı tek olduğunda yanıt s uzunluğudur; aksi hâlde s uzunluğundan sayısı tek olan harflerin sayısı çıkarılır ve 1 eklenir.

def longestPalindrome(s):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

s = "coddyCode"

Beklenen Çıktı