字符串的最大分割长度，使得字符串中的每个字符都出现在一个子字符串中

在本文中，我们将探讨如何找到具有唯一字符的字符串的最大化分区的长度问题。我们首先了解问题陈述，然后研究解决这个问题的朴素和高效方法，包括它们各自的算法和时间复杂度。最后，我们将在C++中实现解决方案。

问题陈述

给定一个字符串，将字符串分割为尽可能多的子字符串，使得字符串中的每个字符只出现在一个子字符串中。返回这些最大化分割的长度。

天真的方法

天真的方法是通过字符串迭代，记录每个字符的最后出现位置。然后，再次迭代字符串，并在找到当前字符的最后出现位置时创建分区。

算法（朴素）

• 初始化一个数组以存储字符串中每个字符的最后出现位置。

• 遍历字符串并记录每个字符的最后出现。

• 初始化一个向量来存储分区的长度。

• 再次遍历字符串，并在找到当前字符的最后出现时创建分区。

C++ 代码（朴素）

Example

示例

#include 
#include 
#include 
#include 

std::vector partitionLengths(std::string s) {
   std::vector lastOccurrence(26, -1);
   
   for (size_t i = 0; i < s.size(); i++) {
      lastOccurrence[s[i] - 'a'] = i;
   }
   
   std::vector 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 lengths = partitionLengths(s);
   
   std::cout << "Lengths of maximized partitions: ";
   for (int length : lengths) {
      std::cout << length << " ";
   }
   
   return 0;
}

输出

Lengths of maximized partitions: 3 3 

时间复杂度（朴素算法） - O(n)，其中n是字符串的长度。

ChatX翻译

最实用、可靠的社交类实时翻译工具。 支持全球主流的20+款社交软件的聊天应用，全球200+语言随意切换。 让您彻底告别复制粘贴的翻译模式，与世界各地高效连接！

下载

高效的方法

高效的方法类似于简单的方法，但我们可以创建分区，同时记录单次迭代中每个字符的最后一次出现，而不是迭代字符串两次。

算法（高效）

• 初始化一个数组以存储字符串中每个字符的最后出现位置。

• 初始化一个向量来存储分区的长度。

• 遍历字符串，记录每个字符的最后出现位置，并在找到当前字符的最后出现位置时创建分区。

C++代码（高效）

示例

#include 
#include 
#include 
#include 

std::vector partitionLengths(std::string s) {
   std::vector lastOccurrence(26, -1);
   std::vector 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 lengths = partitionLengths(s);
   
   std::cout << "Lengths of maximized partitions: ";
   for (int length : lengths) {
      std::cout << length << " ";
   }
   
   return 0;
}

输出

Lengths of maximized partitions: 3 3 

时间复杂度（高效） - O(n)，其中 n 是字符串的长度。

结论

在本文中，我们探讨了查找具有唯一字符的字符串的最大化分区长度的问题。我们讨论了解决这个问题的简单而有效的方法，以及它们的算法和时间复杂度。这种有效的方法结合了记录每个字符的最后一次出现和在单次迭代中创建分区，提供了优化的解决方案。两种方法具有相同的时间复杂度，但有效的方法使用更少的迭代。