Cari Subrentetan Khas Terpanjang Yang Berlaku Tiga Kali I

2981. Cari Subrentetan Khas Terpanjang Yang Berlaku Tiga Kali Saya

Kesukaran: Sederhana

Topik: Jadual Hash, Rentetan, Carian Binari, Tetingkap Gelongsor, Mengira

Anda diberi rentetan s yang terdiri daripada huruf Inggeris huruf kecil.

Rentetan dipanggil istimewa jika ia terdiri daripada satu aksara sahaja. Contohnya, rentetan "abc" tidak istimewa, manakala rentetan "ddd", "zz" dan "f" adalah istimewa.

Kembalikan panjang subrentetan istimewa terpanjang s yang berlaku sekurang-kurangnya tiga kali, atau -1 jika tiada subrentetan khas berlaku sekurang-kurangnya tiga kali.

subrentetan ialah jujukan bukan kosong bersebelahan bagi aksara dalam rentetan.

Contoh 1:

• Input: s = "aaaa"
• Output: 2
• Penjelasan: Subrentetan khas terpanjang yang berlaku tiga kali ialah "aa": subrentetan "aaaa", "aaaa" dan "aaaa".
  • Ia boleh ditunjukkan bahawa panjang maksimum yang boleh dicapai ialah 2.

Contoh 2:

• Input: s = "abcdef"
• Output: -1
• Penjelasan: Tiada subrentetan khas yang berlaku sekurang-kurangnya tiga kali. Oleh itu kembalikan -1.

Contoh 3:

• Input: s = "abcdef"
• Output: 1
• Penjelasan: Subrentetan khas terpanjang yang berlaku tiga kali ialah "a": subrentetan "abcaba", "abcaba" dan "abcaba".
  • Ia boleh ditunjukkan bahawa panjang maksimum yang boleh dicapai ialah 1.

Kekangan:

• 3 <= s.panjang <= 50
• s hanya terdiri daripada huruf kecil Inggeris.

Petunjuk:

1. Kekangannya kecil.
2. Brute force memeriksa semua subrentetan.

Penyelesaian:

Kita boleh menggunakan pendekatan kekerasan kerana kekangan kecil s (panjang sehingga 50). Kami akan:

1. Lelaran ke atas kemungkinan panjang subrentetan (daripada terpanjang kepada terpendek).
2. Semak semua subrentetan panjang yang diberikan dan kira kejadiannya.
3. Jika subrentetan berlaku sekurang-kurangnya tiga kali, semak sama ada ia istimewa (diperbuat daripada satu aksara berulang).
4. Kembalikan panjang subrentetan yang paling panjang. Jika tiada subrentetan memenuhi syarat, kembalikan -1.

Mari laksanakan penyelesaian ini dalam PHP: 2981. Cari Subrentetan Khas Terpanjang Yang Berlaku Tiga Kali Saya

  
  
  Penjelasan:




Gelung Luar: Kami mengulangi kemungkinan panjang subrentetan, bermula dengan yang paling panjang. Ini memastikan kami mengembalikan subrentetan khas terpanjang sebaik sahaja kami menemuinya.

Tetingkap Gelongsor: Untuk setiap panjang subrentetan, kami menggunakan pendekatan tetingkap gelongsor untuk mengekstrak semua subrentetan panjang itu.

Mengira Subrentetan: Kami menggunakan tatasusunan bersekutu ($countMap) untuk menyimpan dan mengira kejadian setiap subrentetan.

Menyemak Istimewa: Fungsi pembantu ialahSemakan khas jika subrentetan terdiri daripada satu aksara berulang sahaja.

Mengembalikan Keputusan: Jika subrentetan yang sah ditemui, kami mengembalikan panjangnya; jika tidak, kami kembalikan -1.



  
  
  Kerumitan




Kerumitan Masa: O(n3) dalam kes yang paling teruk kerana kami:


Lelaran ke atas n panjang subrentetan.
Ekstrak O(n) subrentetan untuk setiap panjang.
Semak sama ada setiap subrentetan adalah istimewa, yang mengambil masa O(n).



Kerumitan Angkasa: O(n2) disebabkan oleh peta pengiraan subrentetan.


Pendekatan kekerasan ini boleh dilaksanakan memandangkan kekangan (n <= 50).

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 Cari Subrentetan Khas Terpanjang Yang Berlaku Tiga Kali I. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!