Leetcode 768 Solution
This article provides solution to leetcode question 768 (partition-labels)
Access this page by simply typing in "lcs 768" in your browser address bar if you have bunnylol configured.
Leetcode Question Link
https://leetcode.com/problems/partition-labels
Solution
class Solution {
public:
vector<int> partitionLabels(string S) {
vector<pair<int, int>> a;
a.resize(26);
for (int i = 0; i < 26; i++)
a[i] = make_pair(-1, -1);
for (int i = 0; i < S.size(); i++)
{
int j = S[i] - 'a';
if (a[j].first == -1)
a[j].first = i;
a[j].second = i;
}
sort(a.begin(), a.end());
int start = -1;
int end = -1;
vector<int> ans;
for (int i = 0; i < a.size(); i++)
{
if (a[i].first == -1)
continue;
if (start == -1)
{
start = a[i].first;
end = a[i].second;
}
else if (a[i].second > end)
end = a[i].second;
if (i == a.size() - 1 || end < a[i + 1].first)
{
ans.push_back(end - start + 1);
start = -1;
end = -1;
}
}
return ans;
}
};