763. Partition Labels
1. Description
A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.
2. Example
Example 1:
Input: S = “ababcbacadefegdehijhklij”
Output: [9,7,8]
Explanation:
The partition is “ababcbaca”, “defegde”, “hijhklij”.
This is a partition so that each letter appears in at most one part.
A partition like “ababcbacadefegde”, “hijhklij” is incorrect, because it splits S into less parts.
3. Note
- S will have length in range [1, 500].
- S will consist of lowercase English letters (‘a’ to ‘z’) only.
4. Solutions
My Accepted Solution
n = i_letters.size()
Time complexity: O(n)
Space complexity: O(ALPHABET_COUNT)
// Greedy
// We want to get more partitions while all duplicate letters should locate in the same partition,
// so we need to let every partition has the least number of letters.
// Therefore, the algorithm is find the first letter, and set its index as left border, then find
// its last index in the string as the right border. Iterate all letters during the range and check
// whether we have to extend the right border. If we go through the string and get to the right
// border, we find a valid least partition.
class Solution {
public:
// vector<int> partitionLabels(string S)
vector<int> partitionLabels(const string& i_letters) {
array<int, ALPHABET_COUNT> letterLastIndex{};
for (int i = 0; i < i_letters.size(); ++i) {
letterLastIndex[toIndex(i_letters[i])] = i;
}
vector<int> partitionsLength;
for (int i = 0, left = 0, right = letterLastIndex[toIndex(i_letters[i])];
i < i_letters.size();
++i) { // i_letters isn't empty(), so i_letters[i] will not out_of_range
if (i == right) {
partitionsLength.push_back(right - left + 1);
left = right + 1;
if (left < i_letters.size()) {
right = letterLastIndex[toIndex(i_letters[left])];
}
}
right = max(letterLastIndex[toIndex(i_letters[i])], right);
}
return partitionsLength;
}
private:
// I hate magic numbers
static const int ALPHABET_COUNT = 26;
inline int toIndex(char letter) {
return letter - 'a';
}
};