763. Partition Labels

763. Partition Labels (Medium)

A string S of lowercase 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.

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.

Note:

1. S will have length in range [1, 500].
2. S will consist of lowercase letters ('a' to 'z') only.

Companies:
Amazon

Related Topics:
Two Pointers, Greedy

Similar Questions:

• Merge Intervals (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/partition-labels/
// Author: github.com/lzl124631x
// Time: O(S)
// Space: O(1)
class Solution {
public:
    vector<int> partitionLabels(string S) {
        int cnt[26] = {};
        for (char c : S) cnt[c - 'a']++;
        vector<int> ans;
        for (int i = 0, prev = 0; i < S.size();) {
            unordered_map<int, int> m;
            do {
                int key = S[i++] - 'a';
                m[key]++;
                if (m[key] == cnt[key]) m.erase(key);
            } while (m.size());
            ans.push_back(i - prev);
            prev = i;
        }
        return ans;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/partition-labels/
// Author: github.com/lzl124631x
// Time: O(S)
// Space: O(1)
class Solution {
public:
    vector<int> partitionLabels(string S) {
        int N = S.size();
        vector<int> right(26), ans;
        for (int i = 0; i < N; ++i) right[S[i] - 'a'] = i;
        int L = 0, R = 0, i = 0;
        while (i < N) {
            L = i, R = right[S[i] - 'a'];
            while (i <= R) {
                R = max(R, right[S[i] - 'a']);
                ++i;
            }
            ans.push_back(R - L + 1);
        }
        return ans;
    }
};