Longest Palindrome

Q: Berapa kompleksitas waktu dari Palindrome Terpanjang?

Waktu O(n) dengan penghitungan: setiap huruf menambahkan 1 ke salah satu penghitung, dan menjumlahkan pasangan membaca 128 penghitung berapa pun panjang s . Ruangnya O(1) . Mengurutkan dan memasangkan elemen yang bersebelahan membutuhkan waktu O(n log n) dan ruang O(n) .

MudahHashing Greedy

+10

Kamu mendapatkan string s yang terdiri dari huruf besar dan huruf kecil. Susun ulang huruf-hurufnya untuk membentuk palindrome sepanjang mungkin, lalu kembalikan panjang palindrome tersebut. Kamu boleh mengatur huruf dalam urutan apa pun dan tidak menggunakan beberapa huruf, tetapi kamu hanya boleh menggunakan setiap huruf sebanyak jumlah kemunculannya di s.

Huruf besar dan huruf kecil dianggap sebagai huruf yang berbeda, jadi Aa bukan palindrome.

Fungsi

longestPalindrome(s: string) → integer

sstring: huruf yang boleh kamu gunakan, huruf besar dan huruf kecil
Mengembalikaninteger: panjang palindrom terpanjang yang bisa kamu buat dari huruf-huruf tersebut

Batasan

1 ≤ s.length ≤ 5 × 10⁴
s hanya berisi huruf alfabet Inggris, a hingga z dan A hingga Z.
Kamu tidak harus menggunakan setiap huruf.

Contoh

Input: s = "coddyCode"
Output: 5
Penjelasan: o muncul dua kali dan d muncul tiga kali, sisanya masing-masing sekali. Sepasang o, sepasang d, dan satu huruf tersisa di tengah menghasilkan panjang 5, misalnya doCod.

Input: s = "Aa"
Output: 1
Penjelasan: A dan a adalah huruf yang berbeda, jadi tidak ada pasangan. Satu huruf saja merupakan palindrom dengan panjang 1.

Input: s = "xxxyyy"
Output: 5
Penjelasan: Dua x dan dua y membentuk pasangan, dan satu huruf yang tersisa diletakkan di tengah, seperti pada xyxyx. Huruf y terakhir tidak memiliki pasangan dan tetap di luar.

Pertanyaan lanjutan

Bisakah kamu mengembalikan satu palindrom terpanjang itu sendiri, beserta panjangnya, tetap dalam waktu O(n)?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Karena kamu boleh menyusun ulang, urutan s tidak penting, yang penting hanya berapa kali setiap huruf muncul. Dalam palindrome, setiap huruf memiliki pasangan cermin di sisi lainnya, kecuali paling banyak satu huruf di tengah. Jadi, hitung hurufnya, pertahankan setiap pasangan, lalu tambahkan satu huruf tengah jika ada huruf yang tersisa.

Urutkan dan pasangkan tetangga

Intuisi

Pengurutan menempatkan huruf yang sama berdampingan, sehingga setiap pasangan berada bersebelahan. Dalam xxxyyy, x pada indeks 0 dan 1 cocok: ambil pasangan itu dan maju dua posisi. Pada indeks 2, x dan y berbeda, jadi x itu tidak berpasangan dan kamu maju satu posisi. y pada indeks 3 dan 4 membentuk pasangan kedua, dan y terakhir tersisa sendiri. Dua pasangan menghasilkan 4, ditambah satu huruf di tengah: 5.

Sebuah huruf tersisa tepat ketika pasangan yang digunakan berjumlah kurang dari semua n huruf, jadi kamu tidak memerlukan penanda terpisah. Pengurutan memerlukan waktu O(n log n), dan salinan yang sudah diurutkan memerlukan ruang O(n).

Algoritma

Urutkan huruf-huruf dalam s.
Telusuri huruf-huruf yang sudah diurutkan dengan indeks i. Jika huruf pada indeks i dan i+1 sama, tambahkan 2 ke panjangnya dan maju dua posisi; jika tidak, maju satu posisi.
Jika panjangnya kurang dari jumlah huruf, tambahkan 1 untuk huruf tengah.
Kembalikan panjangnya.

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

Hitung setiap huruf

Intuisi

Penghitungan memberikan informasi yang sama tanpa pengurutan. Simpan satu penghitung untuk setiap kode karakter, totalnya 128, sehingga A dan a masuk ke penghitung yang berbeda. Huruf yang muncul sebanyak c kali menyumbangkan c yang dibulatkan ke bawah menjadi bilangan genap.

Untuk coddyCode, pasangan o dan d menghasilkan 4 huruf. Lima huruf tersisa tidak digunakan, dan salah satunya dapat ditempatkan di tengah: 5. Huruf kedua yang tidak berpasangan tidak memiliki pasangan cermin.

Satu kali penelusuran s mengisi penghitung dan satu kali penelusuran atas 128 penghitung menjumlahkan pasangan: waktu O(n) dan ruang ekstra O(1) (O(n) di R, yang terlebih dahulu mengubah s menjadi vektor kode).

Algoritma

Buat 128 penghitung yang diatur ke 0, lalu tambahkan 1 ke penghitung untuk setiap huruf dalam s.
Untuk setiap penghitung, tambahkan jumlahnya yang dibulatkan ke bawah menjadi bilangan genap ke panjangnya.
Jika panjangnya kurang dari panjang s, berarti ada jumlah yang ganjil, jadi tambahkan 1 untuk huruf tengah.
Kembalikan panjangnya.

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

Jebakan dan kasus tepi

Mengabaikan jumlah ganjil sepenuhnya. Huruf yang muncul 3 kali tetap menyumbang satu pasangan: xxxyyy menghasilkan 5, bukan 1.
Menambahkan 1 untuk setiap jumlah ganjil. Hanya satu huruf yang bisa berada di tengah, jadi xxxyyy menghasilkan 5, bukan 6.
Menganggap A dan a sebagai huruf yang sama. Aa tidak memiliki pasangan, jadi jawabannya 1, bukan 2.
Membatasi ukuran penghitung hanya untuk a sampai z. Huruf besar memiliki kode 65 sampai 90 dan berada di luar rentang tersebut; gunakan kode karakter lengkap sebagai indeks.

Pertanyaan yang sering diajukan3

Apa perbedaan Palindrom Terpanjang dengan Substring Palindromik Terpanjang?

Di sini kamu dapat menyusun ulang huruf, jadi hanya jumlahnya yang penting dan menghitungnya dapat menyelesaikan soal ini dalam O(n). Longest Palindromic Substring meminta palindrom yang sudah muncul sebagai rangkaian huruf berurutan, dan membutuhkan metode lain, seperti memperluas dari setiap pusat. Untuk abab, soal ini menghasilkan jawaban 4 (abba), sedangkan versi substring menghasilkan 3 (aba).

Berapa kompleksitas waktu dari Palindrome Terpanjang?

Waktu O(n) dengan penghitungan: setiap huruf menambahkan 1 ke salah satu penghitung, dan menjumlahkan pasangan membaca 128 penghitung berapa pun panjang s. Ruangnya O(1). Mengurutkan dan memasangkan elemen yang bersebelahan membutuhkan waktu O(n log n) dan ruang O(n).

Apakah kamu harus menggunakan setiap huruf dari s?

Tidak. Setiap pasangan masuk, dan paling banyak satu huruf yang tidak berpasangan masuk di tengah. Jadi, jawabannya adalah panjang s jika paling banyak ada satu huruf dengan jumlah ganjil, dan jika tidak, panjang s dikurangi jumlah huruf dengan jumlah ganjil, lalu ditambah 1.

def longestPalindrome(s):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "coddyCode"

Output yang diharapkan