Problem Statement:

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

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.

Example 2:

Input: s = "eccbbbbdec"
Output: [10]

Constraints:

1 <= s.length <= 500
s consists of lowercase English letters.

Solution:

From the question, it is clear that we will need the last position where each character appears. For this we create an array positions of length 26. Starting from i=0, we track the value of this “last position” in variable end. Before reaching end, if we find a violation ie see a character whose last appearance is after end then we update end. If we are able to reach end then, we just completed a partition. From here we create a new start for the next partition and continue the process. In this way we find all the partitions.

 
class Solution {
public:
    vector<int> partitionLabels(string s) 
    {
        int n = s.length(), start=-1, end=0;
        vector<int> res, positions(26,-1);
        for(int i=0; i<n; i++) positions[s[i]-'a'] = i;
        for(int i=0; i<n; i++)
        {
            end = max(end, positions[s[i]-'a']);
            if(i==end)
            {
                res.push_back(end-start);
                start=i;
            }
        }
        return res;
    }
};

 
TC: O(n)
SC: O(n)