Susunan Alindromik Panjang Unik

1930. Urutan Palindromik Panjang Unik-3

Kesukaran: Sederhana

Topik: Jadual Hash, Rentetan, Manipulasi Bit, Jumlah Awalan

Diberi rentetan s, kembalikan bilangan palindrom unik sepanjang tiga yang merupakan urutan s.

Perhatikan bahawa walaupun terdapat pelbagai cara untuk mendapatkan urutan yang sama, ia masih dikira sekali sahaja.

palindrom ialah rentetan yang membaca ke hadapan dan ke belakang yang sama.

Satu urutan rentetan ialah rentetan baharu yang dijana daripada rentetan asal dengan beberapa aksara (boleh tiada) dipadamkan tanpa mengubah susunan relatif aksara yang tinggal.

• Sebagai contoh, "ace" ialah susulan daripada "abcde".

Contoh 1:

• Input: s = "aabca"
• Output: 3
• Penjelasan: 3 urutan palindromik panjang 3 ialah:
  • "aba" (susulan daripada "aabca")
  • "aaa" (susulan daripada "aabca")
  • "aca" (susulan daripada "aabca")

Contoh 2:

• Input: s = "adc"
• Output: 0
• Penjelasan: Tiada jujukan palindromik panjang 3 dalam "adc".

Contoh 3:

• Input: s = "bbcbaba"
• Output: 4
• Penjelasan: 4 urutan palindromik panjang 3 ialah:
  • "bbb" (susulan daripada "bbcbaba")
  • "bcb" (susulan daripada "bbcbaba")
  • "bab" (susulan daripada "bbcbaba")
  • "aba" (susulan daripada "bbcbaba")

Kekangan:

• 3 5
• s hanya terdiri daripada huruf kecil Inggeris.

Petunjuk:

1. Berapakah bilangan maksimum panjang-3 rentetan palindromik?
2. Bagaimanakah kita boleh menjejaki watak yang muncul di sebelah kiri kedudukan tertentu?

Penyelesaian:

Kami boleh menggunakan algoritma cekap yang memanfaatkan penjejakan aksara awalan dan akhiran untuk mengira semua urutan palindromik yang sah.

Pendekatan

1. Jejak Aksara Awalan:
   Gunakan tatasusunan untuk menyimpan set aksara yang ditemui di sebelah kiri setiap kedudukan dalam rentetan. Ini akan membantu dalam menyemak dengan cekap sama ada watak boleh membentuk bahagian pertama daripada urutan palindromik.

2. Jejak Aksara Akhiran:
   Gunakan tatasusunan lain untuk menyimpan set aksara yang ditemui di sebelah kanan setiap kedudukan dalam rentetan. Ini akan membantu dalam menyemak dengan cekap sama ada watak boleh membentuk bahagian ketiga daripada urutan palindromik.

3. Kira Susunan Palindromik:
   Untuk setiap aksara dalam rentetan, anggap ia sebagai watak tengah palindrom panjang-3. Semak semua gabungan aksara awalan dan akhiran yang sah untuk menentukan palindrom unik.

4. Hasil Kedai:
   Gunakan set cincang untuk menyimpan urutan palindromik unik, memastikan tiada pendua.

Mari laksanakan penyelesaian ini dalam PHP: 1930. Susunan Palindromik Panjang Unik-3

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

// Test cases
echo countPalindromicSubsequence("aabca") . PHP_EOL; // Output: 3
echo countPalindromicSubsequence("adc") . PHP_EOL;   // Output: 0
echo countPalindromicSubsequence("bbcbaba") . PHP_EOL; // Output: 4
?>

Penjelasan:

1. Susun Awalan:

   • Untuk setiap aksara pada kedudukan i, awalan[i] menyimpan semua aksara berbeza yang ditemui sebelum indeks i.

2. Susun Imbuhan:

   • Untuk setiap aksara pada kedudukan i, akhiran[i] menyimpan semua aksara berbeza yang ditemui selepas indeks i.

3. Watak Pertengahan:

   • Anggap setiap watak sebagai tengah palindrom. Untuk setiap gabungan aksara awalan dan akhiran yang sepadan dengan aksara tengah, bentuk palindrom panjang-3.

4. Peta Hash:

   • Gunakan tatasusunan bersekutu ($uniquePalindromes) untuk menyimpan palindrom unik, memastikan pendua tidak dikira.

Kerumitan

• Kerumitan Masa: O(n)

  • Melintasi rentetan dua kali untuk mengira tatasusunan awalan dan akhiran.
  • Perjalanan ketiga menyemak urutan palindromik yang sah.

• Kerumitan Angkasa: O(n)

  • Untuk tatasusunan awalan dan akhiran.

Keluaran

Kod menghasilkan hasil yang betul untuk contoh yang diberikan:

• Input: "aabca" → Output: 3
• Input: "adc" → Output: 0
• Input: "bbcbaba" → Output: 4

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 Susunan Alindromik Panjang Unik. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!