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 fewer parts.

Example 2

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

Constraints

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

Solution: Find and extend minimal parts

For each character of s, find the last occurrence to identify the minimal part. Extend this part if some other characters inside it have the last occurrence exceeding the part.

Example 1

For s = "ababcbacadefegdehijhklij":

• The first character 'a' gives you its minimal part "ababcbaca". No character inside this part has the last occurrence exceeds it.
• The next character 'd' gives you its minimal part "defegd". But the last occurrence of 'e' inside this part exceeds it. The part becomes "defegde".
• The next character 'h' gives you its minimal part "hijh". But the last occurrence of 'j' exceeds it. The part becomes "hijhklij". End.

Code

#include <vector>
#include <string>
#include <iostream>
using namespace std;
vector<int> partitionLabels(string s) {
    vector<int> result;
    int start = 0;
    while (start < s.length()) {        
        auto lastPos = s.rfind(s[start]);
        for (int j = start; j < lastPos; j++) {
            lastPos = max(lastPos, s.rfind(s[j]));
        }
        result.push_back(lastPos - start + 1);
        start = lastPos + 1;
    }
    return result;
}
void printResult(vector<int>& result) {
    cout << "[";
    for (int a : result) {
        cout << a << ",";
    }
    cout << "]\n";
}
int main() {
    auto result = partitionLabels("ababcbacadefegdehijhklij");
    printResult(result);
    result = partitionLabels("eccbbbbdec");
    printResult(result);
}

Output:
[9,7,8,]
[10,]

Complexity

• Runtime: O(N^2), where N = s.length.
• Extra space: O(1).

Solution 2: Find the last occurrences before computing the parts

In the solution above, the searching s.rfind(c) is repeated if character c appears multiple times in s. You could store those searching before computing the parts to avoid the refinding.

Code

#include <vector>
#include <string>
#include <iostream>
#include <unordered_map>
using namespace std;
vector<int> partitionLabels(string s) {
    vector<int> result;
    unordered_map<char, int> lastPos;
    for (int i = 0; i < s.length(); i++) {
        lastPos[s[i]] = i;
    }    
    int start = 0;
    while (start < s.length()) {
        auto curLastPos = lastPos[s[start]];
        for (int j = start + 1; j < curLastPos; j++) {
            curLastPos = max(curLastPos, lastPos[s[j]]);
        }
        result.push_back(curLastPos - start + 1);
        start = curLastPos + 1;
    }
    return result;
}
void printResult(vector<int>& result) {
    cout << "[";
    for (int a : result) {
        cout << a << ",";
    }
    cout << "]\n";
}
int main() {
    auto result = partitionLabels("ababcbacadefegdehijhklij");
    printResult(result);
    result = partitionLabels("eccbbbbdec");
    printResult(result);
}

Output:
[9,7,8,]
[10,]

Complexity

• Runtime: O(N), where N = s.length.
• Extra space: O(1). Though a map seems to require O(N), in this problem the map requires only 26 int's for the lowercase letters. It can be considered O(1).