Partition Labels
You are given a string S. We want to partition S into as few parts as possible so that each letter appears in at most one part. Return a list of the length of each part.
Constraints:
- 1 <= S.length <= 500
- S consists of lowercase English letters.
Examples:
Input: "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation: The partition is "ababcbaca", "defegde", and "hijhklij".
Solutions
Two Pointers
We use a two-pointer approach to solve this problem. We first create a map to store the last occurrence of each character in the string. Then we initialize two pointers, anchor and j, to 0. We iterate through the string, and for each character, we update j to be the maximum of j and the last occurrence of the character. If i equals j, it means we have found a partition, so we add the length of the partition to the result and update anchor to i + 1.
vector<int> partitionLabels(string S) {
vector<int> last(26, 0);
for (int i = 0;
i < S.size();
i++) {
last[S[i] - 'a'] = i;
}
vector<int> result;
int anchor = 0;
int j = 0;
for (int i = 0;
i < S.size();
i++) {
j = max(j, last[S[i] - 'a']);
if (i == j) {
result.push_back(i - anchor + 1);
anchor = i + 1;
}
}
return result;
}Follow-up:
How would you solve this problem if the string can contain uppercase letters and digits?
