Sponsored
Sponsored
This approach uses a greedy method where we determine the possible endpoints of each partition by finding the last occurrence of each character. As we iterate through the string, we expand the end of the current partition to the maximum last occurrence index of all characters seen so far. The current partition ends once the current index matches this endpoint.
Time Complexity: O(n), where n is the length of the string, because we iterate over the string a constant number of times.
Space Complexity: O(1), as the space used for storing last occurrences is constant, not dependent on input size.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <stdbool.h>
5
6int* partitionLabels(char* s, int* returnSize) {
7 int last[26] = {0};
8 int length = strlen(s);
9
10 // Record the last occurrence of each character
11 for (int i = 0; i < length; i++) {
12 last[s[i] - 'a'] = i;
13 }
14
15 int* result = (int*)malloc(length * sizeof(int));
16 int resultIndex = 0;
17 int start = 0, end = 0;
18
19 for (int i = 0; i < length; i++) {
20 end = (end > last[s[i] - 'a']) ? end : last[s[i] - 'a'];
21 if (i == end) {
22 result[resultIndex++] = end - start + 1;
23 start = i + 1;
24 }
25 }
26
27 *returnSize = resultIndex;
28 return result;
29}
30This C solution utilizes an array to store the last occurrence index of each character. As we iterate through the string, we calculate the endpoint of the current partition by checking the maximum last occurrence index of the characters seen so far. Once the end of the partition is reached, we record its size and move to the next partition.
Another approach involves performing two passes over the string. The first pass is used to collect the rightmost occurrence of each character, and in the second pass, we calculate the sizes of partitions while maintaining the maximum index of characters on the go.
Time Complexity: O(n) for length n of the string, taking linear scans for mapping and partitioning.
Space Complexity: O(1) since the space needed does not grow in relation to input size.
1#include <iostream>
#include <vector>
#include <string>
std::vector<int> partitionLabels(std::string s) {
std::vector<int> last(26, 0);
// Record last occurrence of each character
for (int i = 0; i < s.size(); ++i) {
last[s[i] - 'a'] = i;
}
std::vector<int> result;
int start = 0, end = 0;
for (int i = 0; i < s.size(); ++i) {
end = std::max(end, last[s[i] - 'a']);
if (i == end) {
result.push_back(end - start + 1);
start = i + 1;
}
}
return result;
}
The C++ solution implements a map for storing final indices that dictate string segment limits. On iterating through the string a second time, size intervals are added to the result set recognizing complete segments as index aligns.