Panjang pisah maksimum rentetan supaya setiap aksara dalam rentetan muncul dalam subrentetan

Dalam artikel ini, kami akan meneroka masalah cara mencari panjang partition memaksimumkan rentetan dengan aksara unik. Kami mula-mula memahami penyataan masalah dan kemudian mengkaji kaedah naif dan cekap untuk menyelesaikan masalah ini, termasuk algoritma dan kerumitan masa masing-masing. Akhirnya, kami akan melaksanakan penyelesaian dalam C++.

Pernyataan Masalah

Diberi rentetan, pisahkan rentetan kepada seberapa banyak subrentetan yang mungkin supaya setiap aksara dalam rentetan itu muncul dalam satu subrentetan sahaja. Mengembalikan panjang pemisahan memaksimumkan ini.

Kaedah naif

Pendekatan naif adalah untuk mengulang melalui rentetan, merekodkan kejadian terakhir setiap aksara. Kemudian, ulangi rentetan sekali lagi dan buat partition apabila kejadian terakhir aksara semasa ditemui.

Algoritma (naif)

• Memulakan tatasusunan untuk menyimpan kejadian terakhir setiap aksara dalam rentetan.

• Gelung melalui rentetan dan rekod kejadian terakhir setiap aksara.

• Memulakan vektor untuk menyimpan panjang partition.

• Gelung melalui rentetan sekali lagi dan buat partition apabila kejadian terakhir aksara semasa ditemui.

Kod C++ (biasa)

Contoh

Contoh

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

std::vector<int> partitionLengths(std::string s) {
   std::vector<int> lastOccurrence(26, -1);
   
   for (size_t i = 0; i < s.size(); i++) {
      lastOccurrence[s[i] - 'a'] = i;
   }
   
   std::vector<int> partitionLengths;
   int start = 0, end = 0;
   
   for (size_t i = 0; i < s.size(); i++) {
      end = std::max(end, lastOccurrence[s[i] - 'a']);
      if (i == end) {
         partitionLengths.push_back(end - start + 1);
         start = i + 1;
      }
   }
   
   return partitionLengths;
}

int main() {
   std::string s = "abacdc";
   std::vector<int> lengths = partitionLengths(s);
   
   std::cout << "Lengths of maximized partitions: ";
   for (int length : lengths) {
      std::cout << length << " ";
   }
   
   return 0;
}

Output

Lengths of maximized partitions: 3 3 

Kerumitan masa (algoritma naif) - O(n), dengan n ialah panjang rentetan.

Kaedah yang cekap

Kaedah yang cekap adalah serupa dengan kaedah yang mudah, tetapi bukannya mengulangi rentetan dua kali, kami boleh mencipta partition sambil merakam kejadian terakhir setiap aksara dalam satu lelaran.

Algoritma (cekap)

• Memulakan tatasusunan untuk menyimpan kejadian terakhir setiap aksara dalam rentetan.

• Mulakan vektor untuk menyimpan panjang partition.

• Gelung melalui rentetan, rekod kejadian terakhir setiap aksara dan buat partition apabila kejadian terakhir aksara semasa ditemui.

Kod C++ (cekap)

Contoh

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

std::vector<int> partitionLengths(std::string s) {
   std::vector<int> lastOccurrence(26, -1);
   std::vector<int> partitionLengths;
   int start = 0, end = 0;
   
   for (size_t i = 0; i < s.size(); i++) {
      lastOccurrence[s[i] - 'a'] = i;
   }
   
   for (size_t i = 0; i < s.size(); i++) {
      end = std::max(end, lastOccurrence[s[i] - 'a']);
   
      if (i == end) {
         partitionLengths.push_back(end - start + 1);
         start = i + 1;
      }
   }
   
   return partitionLengths;
}

int main() {
   std::string s = "abacdc";
   std::vector<int> lengths = partitionLengths(s);
   
   std::cout << "Lengths of maximized partitions: ";
   for (int length : lengths) {
      std::cout << length << " ";
   }
   
   return 0;
}

Output

Lengths of maximized partitions: 3 3 

Kerumitan masa (cekap) - O(n), dengan n ialah panjang rentetan.

Kesimpulan

Dalam artikel ini, kami meneroka masalah memaksimumkan panjang partition untuk mencari rentetan dengan aksara unik. Kami membincangkan kaedah yang mudah tetapi cekap untuk menyelesaikan masalah ini, bersama-sama dengan kerumitan algoritma dan masa mereka. Pendekatan cekap ini menggabungkan rakaman kejadian terakhir bagi setiap aksara dan mencipta sekatan dalam satu lelaran, memberikan penyelesaian yang dioptimumkan. Kedua-dua kaedah mempunyai kerumitan masa yang sama, tetapi kaedah yang cekap menggunakan lebih sedikit lelaran.

Atas ialah kandungan terperinci Panjang pisah maksimum rentetan supaya setiap aksara dalam rentetan muncul dalam subrentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!