The maximum split length of a string such that each character in the string appears in a substring

In this article, we will explore the problem of how to find the length of the maximizing partition of a string with unique characters. We first understand the problem statement and then study naive and efficient methods to solve this problem, including their respective algorithms and time complexities. Finally, we will implement the solution in C.

Problem Statement

Given a string, split the string into as many substrings as possible so that each character in the string appears in only one substring. Returns the length of these maximizing splits.

Naive method

The naive approach is to iterate through the string and record the last occurrence of each character. Then, iterate over the string again and create a partition when the last occurrence of the current character is found.

Algorithm (simple)

• Initialize an array to store the last occurrence of each character in the string.

• Loop through the string and record the last occurrence of each character.

• Initialize a vector to store the length of the partition.

• Loop through the string again and create partitions when the last occurrence of the current character is found.

C code (plain)

Example

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

Output

Lengths of maximized partitions: 3 3 

Time complexity (naive algorithm) - O(n), where n is the length of the string.

Efficient method

The efficient method is similar to the simple method, but instead of iterating the string twice, we can create partitions that simultaneously record the last occurrence of each character in a single iteration.

Algorithm (efficient)

• Initialize an array to store the last occurrence of each character in the string.

• Initialize a vector to store the length of the partition.

• Traverse the string, record the last occurrence of each character, and create a partition when the last occurrence of the current character is found.

C code (efficient)

Example

#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 

Time complexity (efficient) - O(n), where n is the length of the string.

in conclusion

In this article, we explore the problem of maximizing partition length for finding strings with unique characters. We discuss simple yet efficient methods for solving this problem, along with their algorithmic and time complexity. This efficient approach combines recording the last occurrence of each character and creating partitions in a single iteration, providing an optimized solution. Both methods have the same time complexity, but the efficient method uses fewer iterations.

The above is the detailed content of The maximum split length of a string such that each character in the string appears in a substring. For more information, please follow other related articles on the PHP Chinese website!