Panjang Minimum Rentetan Selepas Operasi

3223. Panjang Minimum Rentetan Selepas Operasi

Kesukaran: Sederhana

Topik: Jadual Hash, Rentetan, Mengira

Anda diberi rentetan s.

Anda boleh melakukan proses berikut pada s sebarang bilangan kali:

• Pilih indeks i dalam rentetan supaya terdapat sekurang-kurangnya satu aksara di sebelah kiri indeks i yang sama dengan s[i] dan sekurang-kurangnya satu aksara ke kanan yang juga sama dengan s[i].
• Padam aksara paling dekat ke kiri indeks i yang sama dengan s[i].
• Padam aksara paling hampir ke kanan indeks i yang sama dengan s[i].

Kembalikan panjang minimum rentetan akhir s yang boleh anda capai.

Contoh 1:

• Input: s = "abaacbcbb"
• Output: 5
• Penjelasan: Kami melakukan operasi berikut:
  • Pilih indeks 2, kemudian alih keluar aksara pada indeks 0 dan 3. Rentetan yang terhasil ialah s = "bacbcbb".
  • Pilih indeks 3, kemudian alih keluar aksara pada indeks 0 dan 5. Rentetan yang terhasil ialah s = "acbcb".

Contoh 2:

• Input: s = "aa"
• Output: 2
• Penjelasan: Kami tidak boleh melakukan sebarang operasi, jadi kami mengembalikan panjang rentetan asal.

Kekangan:

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

Petunjuk:

1. Hanya kekerapan setiap watak penting dalam mencari jawapan muktamad.
2. Jika watak berlaku kurang daripada 3 kali, kami tidak boleh melakukan sebarang proses dengannya.
3. Andaikan terdapat aksara yang berlaku sekurang-kurangnya 3 kali dalam rentetan, kita boleh memadam dua daripada aksara ini berulang kali sehingga terdapat paling banyak 2 kejadian yang tinggal daripadanya.

Penyelesaian:

Kita perlu fokus pada kekerapan setiap aksara dalam rentetan. Berikut ialah pendekatan untuk menyelesaikannya:

Pendekatan:

1. Kira Kekerapan Aksara:

   • Gunakan jadual kekerapan untuk mengira berapa kali setiap aksara muncul dalam rentetan.

2. Kurangkan Aksara dengan Kekerapan >= 3:

   • Jika aksara muncul 3 kali atau lebih, kami boleh memadam dua daripadanya berulang kali sehingga hanya tinggal 2 kejadian.

3. Kira Panjang Minimum:

   • Ringkaskan baki kiraan semua aksara selepas mengurangkan frekuensi.

Mari kita laksanakan penyelesaian ini dalam PHP: 3223. Panjang Minimum Rentetan Selepas Operasi


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

// Example 1
$s1 = "abaacbcbb";
echo "Input: $s1\n";
echo "Output: " . minimumLength($s1) . "\n";

// Example 2
$s2 = "aa";
echo "Input: $s2\n";
echo "Output: " . minimumLength($s2) . "\n";
?>

Penjelasan:

1. Kiraan Kekerapan:

   • Lelaran melalui rentetan, dan untuk setiap aksara, tambahkan kiraannya dalam tatasusunan $frequency.

2. Pengurangan Watak:

   • Untuk setiap aksara dalam tatasusunan $frequency, semak sama ada kiraannya ialah 3 atau lebih. Jika ya, kurangkan kepada paling banyak 2.

3. Kira Keputusan:

   • Jumlah nilai dalam tatasusunan $frequency untuk mendapatkan panjang minimum rentetan yang mungkin.

Contoh Panduan:

Contoh 1:

• Input: s = "abaacbcbb"
• Kekerapan: ['a' => 3, 'b' => 4, 'c' => 2]
• Selepas pengurangan:
  • 'a' => 2 (dikurangkan daripada 3),
  • 'b' => 2 (dikurangkan daripada 4),
  • 'c' => 2 (tiada pengurangan diperlukan).
• Panjang minimum: 2 2 2 = 6.

Contoh 2:

• Input: s = "aa"
• Kekerapan: ['a' => 2]
• Tiada pengurangan diperlukan kerana tiada aksara yang mempunyai kekerapan 3 atau lebih.
• Panjang minimum: 2.

Kerumitan:

1. Kerumitan Masa:

   • Mengira frekuensi: O(n), dengan n ialah panjang rentetan.
   • Pengurangan: O(1) (masa tetap, kerana terdapat hanya 26 huruf kecil).
   • Frekuensi penjumlahan: O(1).
   • Keseluruhan: O(n).

2. Kerumitan Angkasa:

   • O(1), memandangkan tatasusunan frekuensi mempunyai paling banyak 26 entri.

Penyelesaian ini cekap dan berfungsi dengan baik dalam kekangan masalah.

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 Panjang Minimum Rentetan Selepas Operasi. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!