Bina K Palindrom Rentetan

1400. Construct K Palindrome Strings

Kesukaran: Sederhana

Topik: Jadual Hash, Rentetan, Tamak, Mengira

Diberi rentetan s dan integer k, kembalikan benar jika anda boleh menggunakan semua aksara dalam s untuk membina rentetan k palindrom atau palsu sebaliknya.

Contoh 1:

• Input: s = "annabelle", k = 2
• Output: benar
• Penjelasan: Anda boleh membina dua palindrom menggunakan semua aksara dalam s.
  • Beberapa kemungkinan binaan "anna" "elble", "anbna" "elle", "anellena" "b"

Contoh 2:

• Input: s = "leetcode", k = 3
• Output: palsu
• Penjelasan: Adalah mustahil untuk membina 3 palindrom menggunakan semua aksara s.

Contoh 3:

• Input: s = "benar", k = 4
• Output: benar
• Penjelasan: Satu-satunya penyelesaian yang mungkin ialah meletakkan setiap aksara dalam rentetan yang berasingan.

Kekangan:

• 1 <= s.panjang <= 10⁵
• s terdiri daripada huruf kecil Inggeris.
• 1 <= k <= 10⁵

Petunjuk:

1. Jika s.panjang < k kita tidak boleh membina rentetan k daripada s dan jawapan adalah palsu.
2. Jika bilangan aksara yang mempunyai kiraan ganjil ialah > k maka bilangan minimum rentetan palindrom yang boleh kita bina ialah > k dan jawapan adalah palsu.
3. Jika tidak, anda boleh membina rentetan k palindrom dengan tepat dan jawapannya adalah benar (mengapa ?).

Penyelesaian:

Kita perlu mempertimbangkan perkara berikut:

Pemerhatian Utama:

1. Ciri-ciri Palindrom:

   • Palindrom ialah rentetan yang membaca ke hadapan dan ke belakang yang sama.
   • Untuk palindrom genap, semua aksara mesti muncul beberapa kali genap.
   • Untuk palindrom panjang ganjil, semua aksara kecuali satu mesti muncul bilangan kali genap (aksara yang muncul bilangan kali ganjil akan berada di tengah).

2. Syarat yang Perlu:

   • Jika panjang s kurang daripada k, adalah mustahil untuk membentuk rentetan k, jadi pulangkan palsu.
   • Jumlah bilangan aksara yang muncul beberapa kali ganjil mestilah paling banyak k untuk membentuk k palindrom. Ini kerana setiap palindrom boleh mempunyai paling banyak satu aksara dengan kiraan ganjil (watak tengah untuk palindrom ganjil panjang).

Pendekatan:

1. Kira kekerapan setiap aksara dalam rentetan.
2. Kira bilangan aksara yang mempunyai kekerapan ganjil.
3. Jika bilangan frekuensi ganjil melebihi k, kembalikan palsu (kerana mustahil untuk membentuk k palindrom).

Mari laksanakan penyelesaian ini dalam PHP: 1400. Construct K Palindrome Strings


<?php
/**
 * @param String $s
 * @param Integer $k
 * @return Boolean
 */
function canConstruct($s, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
var_dump(canConstruct("annabelle", 2)); // Output: true
var_dump(canConstruct("leetcode", 3)); // Output: false
var_dump(canConstruct("true", 4));      // Output: true
?>

Penjelasan:

1. Kira Frekuensi: Kami menggunakan tatasusunan bersekutu $freq untuk mengira kejadian setiap aksara dalam rentetan.
2. Kiraan Ganjil: Kami menyemak bilangan aksara yang mempunyai kejadian ganjil. Ini akan membantu kita menentukan sama ada kita boleh membentuk palindrom.
3. Semakan Keadaan: Jika bilangan aksara dengan frekuensi ganjil lebih besar daripada k, adalah mustahil untuk membentuk k palindrom, jadi kami mengembalikan palsu. Jika tidak, kami kembali benar.

Kerumitan Masa:

• Mengira frekuensi mengambil masa O(n), dengan n ialah panjang rentetan.
• Menyemak frekuensi ganjil mengambil masa O(m), dengan m ialah bilangan aksara yang berbeza (paling banyak 26 untuk huruf Inggeris huruf kecil).
• Kerumitan masa keseluruhan ialah O(n m), yang memudahkan kepada O(n) dalam kes ini.

Kes Tepi:

1. Jika k lebih besar daripada panjang s, kami mengembalikan palsu.
2. Jika semua aksara mempunyai frekuensi genap, kita sentiasa boleh membentuk palindrom, jadi hasilnya bergantung kepada sama ada k mungkin.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci Bina K Palindrom Rentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!