763. Partition Labels

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. For example, the string "ababcc" can be partitioned into ["abab", "cc"], but partitions such as ["aba", "bcc"] or ["ab", "ab", "cc"] are invalid.

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.

Approach 01:

#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> partitionLabels(string s) {
        unordered_map<char, int> lastOccurrence;  
        vector<int> partitions;
        int partitionEnd = 0;
        int partitionSize = 0;

        for (int index = 0; index < s.size(); ++index)
            lastOccurrence[s[index]] = index;

        for (int index = 0; index < s.size(); ++index) {
            partitionEnd = max(partitionEnd, lastOccurrence[s[index]]);
            partitionSize++;

            if (index == partitionEnd) {
                partitions.push_back(partitionSize);
                partitionSize = 0;
            }
        }

        return partitions;
    }
};

from typing import List

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        lastOccurrence = {char: index for index, char in enumerate(s)}  
        partitions = []
        partitionEnd = 0
        partitionSize = 0

        for index, char in enumerate(s):
            partitionEnd = max(partitionEnd, lastOccurrence[char])
            partitionSize += 1
            if index == partitionEnd:
                partitions.append(partitionSize)
                partitionSize = 0  
                
        return partitions

Time Complexity:

• Finding Last Occurrences:

  Iterating through the string to record the last occurrence of each character takes \( O(n) \), where \( n \) is the length of the string.

• Partitioning the String:

  Another pass through the string to determine partitions takes \( O(n) \).

• Total Time Complexity:

  The overall time complexity is \( O(n) \).

Space Complexity:

• Last Occurrence Map:

  The unordered map lastOccurrence stores at most 26 entries (one for each lowercase letter), taking \( O(1) \) space.

• Partition Storage:

  The output list partitions stores partition sizes, which in the worst case can be \( O(n) \).

• Auxiliary Variables:

  A few integer variables (partitionEnd, partitionSize, etc.) take \( O(1) \) space.

• Total Space Complexity:

  The overall space complexity is \( O(n) \) due to the output list.