字串的最大分割長度，使得字串中的每個字元都出現在一個子字串中

在本文中，我們將探討如何找到具有唯一字元的字串的最大化分區的長度問題。我們首先了解問題陳述，然後研究解決這個問題的樸素和高效方法，包括它們各自的演算法和時間複雜度。最後，我們將在C 中實現解決方案。

問題陳述

給定一個字串，將字串分割成盡可能多的子字串，使得字串中的每個字元只出現在一個子字串中。傳回這些最大化分割的長度。

天真的方法

天真的方法是透過字串迭代，記錄每個字元的最後出現位置。然後，再次迭代字串，並在找到當前字元的最後出現位置時建立分區。

演算法（樸素）

• 初始化一個陣列以儲存字串中每個字元的最後出現位置。

• 遍歷字串並記錄每個字元的最後出現。

• 初始化一個向量來儲存分割區的長度。

• 再次遍歷字串，並在找到目前字元的最後出現時建立分割區。

C 程式碼（樸素）

Example

的中文翻譯為：

範例

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

輸出

Lengths of maximized partitions: 3 3 

時間複雜度（樸素演算法） - O(n)，其中n是字串的長度。

高效的方法

高效的方法類似於簡單的方法，但我們可以建立分區，同時記錄單次迭代中每個字元的最後一次出現，而不是迭代字串兩次。

演算法（高效）

• 初始化一個陣列以儲存字串中每個字元的最後出現位置。

• 初始化一個向量來儲存分割區的長度。

• 遍歷字串，記錄每個字元的最後出現位置，並在找到目前字元的最後出現位置時建立分區。

C 程式碼（高效）

範例

#

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

輸出

Lengths of maximized partitions: 3 3 

時間複雜度（高效） - O(n)，其中 n 是字串的長度。

結論

在本文中，我們探討了尋找具有唯一字元的字串的最大化分區長度的問題。我們討論了解決這個問題的簡單而有效的方法，以及它們的演算法和時間複雜度。這種有效的方法結合了記錄每個字元的最後一次出現和在單次迭代中建立分區，提供了最佳化的解決方案。兩種方法具有相同的時間複雜度，但有效的方法使用較少的迭代。

以上是字串的最大分割長度，使得字串中的每個字元都出現在一個子字串中的詳細內容。更多資訊請關注PHP中文網其他相關文章！