Padamkan Aksara untuk Membuat Rentetan Mewah

1957. Padamkan Aksara untuk Membuat Rentetan Mewah

Kesukaran: Mudah

Topik: Rentetan

rentetan mewah ialah rentetan yang tiada tiga aksara berturut-turut adalah sama.

Diberi rentetan s, padamkan minimum bilangan aksara yang mungkin daripada s untuk menjadikannya mewah.

Kembalikan rentetan akhir selepas pemadaman. Ia boleh ditunjukkan bahawa jawapannya akan sentiasa unik.

Contoh 1:

• Input: s = "leeetcode"
• Output: "leetcode"
• Penjelasan: Alih keluar 'e' daripada kumpulan pertama 'e's untuk mencipta "leetcode". Tiada tiga aksara berturut-turut adalah sama, jadi kembalikan "leetcode".

Contoh 2:

• Input: s = "aaabaaaa"
• Output: "aabaa"
• Penjelasan: Alih keluar 'a' daripada kumpulan pertama 'a' untuk mencipta "aabaaaa". Keluarkan dua 'a' daripada kumpulan kedua 'a' untuk mencipta "aabaa". Tiada tiga aksara berturut-turut adalah sama, jadi kembalikan "aabaa".

Contoh 3:

• Input: s = "aab"
• Output: "aab"
• Penjelasan: Tiada tiga aksara berturut-turut adalah sama, jadi kembalikan "aab".

Kekangan:

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

Petunjuk:

1. Apakah cara yang optimum untuk memadam aksara jika tiga atau lebih aksara berturut-turut adalah sama?
2. Jika tiga atau lebih aksara berturut-turut adalah sama, simpan dua daripadanya dan padamkan yang lain.

Penyelesaian:

Kita perlu memastikan bahawa tiada tiga aksara berturut-turut adalah sama dalam rentetan akhir. Kami akan mengulangi rentetan input dan membina rentetan "mewah" baharu dengan menjejaki dua aksara sebelumnya. Jika aksara ketiga berturut-turut sepadan dengan dua watak terakhir, kami melangkaunya. Jika tidak, kami menambahnya pada output.

Mari kita laksanakan penyelesaian ini dalam PHP: 1957. Padamkan Aksara untuk Membuat Rentetan Mewah

  
  
  Penjelasan:




Memulakan Pembolehubah:



$result: Ini akan menyimpan rentetan "fancy" terakhir.



Lelaran melalui Rentetan:


Untuk setiap watak, semak sama ada ia membentuk trio dengan dua aksara terakhir dalam hasilnya.
Jika ya, langkau menambahkannya pada $result.
Jika tidak, tambahkannya pada $result.



Kembalikan Keputusan:

Rentetan $result kini tidak mengandungi tiga aksara yang sama berturut-turut.





  
  
  Analisis Kerumitan




Kerumitan Masa: O(n), dengan n ialah panjang rentetan input, seperti yang kita proses setiap watak sekali.

Kerumitan Angkasa: O(n), untuk menyimpan rentetan output.


Penyelesaian ini memenuhi kekangan dengan cekap dan memastikan rentetan akhir tidak mempunyai tiga aksara yang serupa berturut-turut.

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 Padamkan Aksara untuk Membuat Rentetan Mewah. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!