La longueur maximale de division d'une chaîne de telle sorte que chaque caractère de la chaîne apparaisse dans une sous-chaîne

Dans cet article, nous explorerons le problème de savoir comment trouver la longueur de la partition maximisée d'une chaîne avec des caractères uniques. Nous comprenons d’abord l’énoncé du problème, puis étudions des méthodes naïves et efficaces pour résoudre ce problème, y compris leurs algorithmes respectifs et leurs complexités temporelles. Enfin, nous implémenterons la solution en C++.

Énoncé du problème

À partir d'une chaîne, divisez-la en autant de sous-chaînes que possible afin que chaque caractère de la chaîne apparaisse dans une seule sous-chaîne. Renvoie la longueur de ces divisions maximisées.

Méthode naïve

L'approche naïve consiste à parcourir la chaîne, en enregistrant la dernière occurrence de chaque caractère. Ensuite, parcourez à nouveau la chaîne et créez une partition lorsque la dernière occurrence du caractère actuel est trouvée.

Algorithme (naïf)

• Initialisez un tableau pour stocker la dernière occurrence de chaque caractère dans la chaîne.

• Parcourez la chaîne et enregistrez la dernière occurrence de chaque caractère.

• Initialisez un vecteur pour stocker la longueur de la partition.

• Parcourez à nouveau la chaîne et créez des partitions lorsque la dernière occurrence du caractère actuel est trouvée.

Code C++ (simple)

Exemple

Exemple

#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;
}

Sortie

Lengths of maximized partitions: 3 3 

Complexité temporelle (algorithme naïf) - O(n), où n est la longueur de la chaîne.

Méthode efficace

La méthode efficace est similaire à la méthode simple, mais au lieu d'itérer la chaîne deux fois, nous pouvons créer des partitions tout en enregistrant la dernière occurrence de chaque caractère en une seule itération.

Algorithme (efficace)

• Initialisez un tableau pour stocker la dernière occurrence de chaque caractère dans la chaîne.

• Initialisez un vecteur pour stocker la longueur de la partition.

• Parcourez la chaîne, enregistrez la dernière occurrence de chaque caractère et créez une partition lorsque la dernière occurrence du caractère actuel est trouvée.

Code C++ (efficace)

Exemple

#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;
}

Sortie

Lengths of maximized partitions: 3 3 

Complexité temporelle (efficace) - O(n), où n est la longueur de la chaîne.

Conclusion

Dans cet article, nous explorons le problème de la maximisation de la longueur de la partition pour trouver des chaînes avec des caractères uniques. Nous discutons de méthodes simples mais efficaces pour résoudre ce problème, ainsi que de leur complexité algorithmique et temporelle. Cette approche efficace combine l'enregistrement de la dernière occurrence de chaque caractère et la création de partitions en une seule itération, offrant ainsi une solution optimisée. Les deux méthodes ont la même complexité temporelle, mais la méthode efficace utilise moins d’itérations.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!