Home > Backend Development > C++ > body text

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

WBOY
Release: 2023-08-25 14:41:18
forward
988 people have browsed it

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)

The Chinese translation of

Example

is:

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;
}
Copy after login

Output

Lengths of maximized partitions: 3 3 
Copy after login
Copy after login

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;
}
Copy after login

Output

Lengths of maximized partitions: 3 3 
Copy after login
Copy after login

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!

source:tutorialspoint.com
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template