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

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

问题陈述

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

朴素方法

朴素方法是遍历字符串，记录每个字符的最后一次出现位置。然后，再次遍历字符串并在找到当前字符的最后一次出现位置时创建分区。

算法（朴素）

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

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

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

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

代码（朴素）

示例

以下是上述算法的程序：

C C++ Java Python
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* partitionLengths(char* s, int* returnSize) {
   // Allocate memory for storing the last occurrence index of each character
   int* lastOccurrence = (int*)malloc(26 * sizeof(int));
   for (int i = 0; i < 26; i++) {
      lastOccurrence[i] = -1; // Initialize to -1, indicating character not encountered yet
   }
    
   int len = strlen(s);
   for (int i = 0; i < len; i++) {
      lastOccurrence[s[i] - 'a'] = i; // Update last occurrence index of character
   }
    
   // Allocate memory for storing partition lengths
   int* partitionLengths = (int*)malloc(len * sizeof(int));
   int start = 0, end = 0, partitionCount = 0;
    
   for (int i = 0; i < len; i++) {
      // Update end with maximum of its current value and the last occurrence index of current character
      end = (end > lastOccurrence[s[i] - 'a']) ? end : lastOccurrence[s[i] - 'a'];
        
      if (i == end) {
         // A partition has ended, calculate its length and store it
         partitionLengths[partitionCount++] = end - start + 1;
         start = i + 1; // Move the start of the next partition
      }
   }
    
   *returnSize = partitionCount; // Set the size of the result array
   return partitionLengths; // Return the array of partition lengths
}

int main() {
   char s[] = "abacdc";
   int length;
   int* lengths = partitionLengths(s, &length);
    
   printf("Lengths of maximized partitions: ");
   for (int i = 0; i < length; i++) {
      printf("%d ", lengths[i]);
   }
    
   free(lengths);
   return 0;
}

输出

Lengths of maximized partitions: 3 3

#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

import java.util.ArrayList;
import java.util.List;

public class Main {
   public static List<Integer> partitionLengths(String s) {
      int[] lastOccurrence = new int[26];
      for (int i = 0; i < 26; i++) {
         lastOccurrence[i] = -1; // Initialize to -1, indicating character not encountered yet
      }
        
      for (int i = 0; i < s.length(); i++) {
         lastOccurrence[s.charAt(i) - 'a'] = i; // Update last occurrence index of character
      }
        
      List<Integer> partitionLengths = new ArrayList<>(); // List to store partition lengths
      int start = 0, end = 0;
        
      for (int i = 0; i < s.length(); i++) {
         // Update end with maximum of its current value and the last occurrence index of current character
         end = Math.max(end, lastOccurrence[s.charAt(i) - 'a']);
         
         if (i == end) {
            // A partition has ended, calculate its length and store it
            partitionLengths.add(end - start + 1);
            start = i + 1; // Move the start of the next partition
         }
      }
        
      return partitionLengths;
   }

   public static void main(String[] args) {
      String s = "abacdc";
      List<Integer> lengths = partitionLengths(s);
        
      System.out.print("Lengths of maximized partitions: ");
      for (int length : lengths) {
         System.out.print(length + " ");
      }
   }
}

输出

Lengths of maximized partitions: 3 3

def partition_lengths(s):
   # Initialize a list to store the last occurrence index of each character
   last_occurrence = [-1] * 26
    
   # Update the last occurrence index of each character
   for i in range(len(s)):
      last_occurrence[ord(s[i]) - ord('a')] = i
    
   partition_lengths = []  # List to store partition lengths
   start = end = 0
    
   for i in range(len(s)):
      # Update end with maximum of its current value and the last occurrence index of current character
      end = max(end, last_occurrence[ord(s[i]) - ord('a')])
        
      if i == end:
         # A partition has ended, calculate its length and store it
         partition_lengths.append(end - start + 1)
         start = i + 1  # Move the start of the next partition
            
   return partition_lengths

def main():
   s = "abacdc"
   lengths = partition_lengths(s)
    
   print("Lengths of maximized partitions:", end=" ")
   for length in lengths:
      print(length, end=" ")

if __name__ == "__main__":
   main()

输出

Lengths of maximized partitions: 3 3

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

高效方法

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

算法（高效）

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

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

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

代码（高效）

示例

以下是上述算法的程序：

C C++ Java Python
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* partitionLengths(char* s, int* returnSize) {
   // Create an array to store the last occurrence index of each character
   int lastOccurrence[26];
   for (int i = 0; i < 26; i++) {
      lastOccurrence[i] = -1; // Initialize to -1 indicating character not encountered yet
   }
    
   int len = strlen(s);
   for (int i = 0; i < len; i++) {
      lastOccurrence[s[i] - 'a'] = i; // Update last occurrence index of character
   }
    
   // Allocate memory for storing partition lengths
   int* partitionLengths = (int*)malloc(len * sizeof(int));
   int start = 0, end = 0, partitionCount = 0;
    
   for (int i = 0; i < len; i++) {
      // Update end with maximum of its current value and the last occurrence index of current character
      end = (end > lastOccurrence[s[i] - 'a']) ? end : lastOccurrence[s[i] - 'a'];
        
      if (i == end) {
         // A partition has ended, calculate its length and store it
         partitionLengths[partitionCount++] = end - start + 1;
         start = i + 1; // Move the start of the next partition
      }
   }
    
   *returnSize = partitionCount; // Set the size of the result array
   return partitionLengths; // Return the array of partition lengths
}

int main() {
   char s[] = "abacdc";
   int length;
   int* lengths = partitionLengths(s, &length);
    
   printf("Lengths of maximized partitions: ");
   for (int i = 0; i < length; i++) {
      printf("%d ", lengths[i]); // Print the lengths of maximized partitions
   }
    
   free(lengths);
   return 0;
}

输出

Lengths of maximized partitions: 3 3

#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

import java.util.ArrayList;
import java.util.List;

public class Main {
   public static List<Integer> partitionLengths(String s) {
      // Create an array to store the last occurrence index of each character
      int[] lastOccurrence = new int[26];
      for (int i = 0; i < 26; i++) {
         lastOccurrence[i] = -1; // Initialize to -1 indicating character not encountered yet
      }
      
      List<Integer> partitionLengths = new ArrayList<>(); // List to store partition lengths
      int start = 0, end = 0;
      
      // Update the last occurrence index of each character
      for (int i = 0; i < s.length(); i++) {
         lastOccurrence[s.charAt(i) - 'a'] = i;
      }
      
      for (int i = 0; i < s.length(); i++) {
         // Update end with maximum of its current value and the last occurrence index of current character
         end = Math.max(end, lastOccurrence[s.charAt(i) - 'a']);
   
         if (i == end) {
            // A partition has ended, calculate its length and store it
            partitionLengths.add(end - start + 1);
            start = i + 1; // Move the start of the next partition
         }
      }
      
      return partitionLengths;
   }

   public static void main(String[] args) {
      String s = "abacdc";
      List<Integer> lengths = partitionLengths(s);
        
      System.out.print("Lengths of maximized partitions: ");
      for (int length : lengths) {
         System.out.print(length + " "); // Print the lengths of maximized partitions
      }
   }
}

输出

Lengths of maximized partitions: 3 3

def partition_lengths(s):
   # Initialize a list to store the last occurrence index of each character
   last_occurrence = [-1] * 26
   partition_lengths = [] # List to store partition lengths
   start = end = 0
    
   # Update the last occurrence index of each character
   for i in range(len(s)):
      last_occurrence[ord(s[i]) - ord('a')] = i
    
   for i in range(len(s)):
      # Update end with maximum of its current value and the last occurrence index of current character
      end = max(end, last_occurrence[ord(s[i]) - ord('a')])
   
      if i == end:
         # A partition has ended, calculate its length and store it
         partition_lengths.append(end - start + 1)
         start = i + 1  # Move the start of the next partition
            
   return partition_lengths

def main():
   s = "abacdc"
   lengths = partition_lengths(s)
    
   print("Lengths of maximized partitions:", end=" ")
   for length in lengths:
      print(length, end=" ")  # Print the lengths of maximized partitions

if __name__ == "__main__":
   main()

输出

Lengths of maximized partitions: 3 3

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

结论

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

更新于: 2023年10月23日

211 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始
广告

© . All rights reserved.