Partition Labels medium

Problem Statement

A string s of lowercase English 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. A partition is a set of disjoint substrings.

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 uses more than one part.

Example 2

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

Steps

1. Last Occurrence Map: Create a hash map (or unordered map in C++) to store the last occurrence index of each character in the string. Iterate through the string, updating the map for each character.

2. Partitioning: Initialize last to 0, which keeps track of the rightmost index of the current partition. Initialize partition_end to 0 which keeps track of the index of the end of a partition. Iterate through the string:

   • For each character, check its last occurrence index from the map.
   • If the last occurrence index is greater than partition_end, update partition_end to this last occurrence index. This means we've found a character that extends the current partition.
   • If the current index i is equal to partition_end, it means we've reached the end of a partition. Add partition_end - last + 1 (the length of the partition) to the result list and update last to partition_end + 1.

3. Return Result: Return the list of partition lengths.

Explanation

The key idea is to find the last occurrence of each character. We only need to extend a partition as long as there's a character whose last occurrence is beyond the current partition's end. Once we reach a point where the current character's last occurrence is within the current partition, we know we've found a complete partition.

Code (C++)

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

std::vector<int> partitionLabels(std::string s) {
    std::unordered_map<char, int> lastOccurrence;
    for (int i = 0; i < s.length(); ++i) {
        lastOccurrence[s[i]] = i;
    }

    std::vector<int> result;
    int last = 0;
    int partitionEnd = 0;
    for (int i = 0; i < s.length(); ++i) {
        partitionEnd = std::max(partitionEnd, lastOccurrence[s[i]]);
        if (i == partitionEnd) {
            result.push_back(partitionEnd - last + 1);
            last = partitionEnd + 1;
        }
    }
    return result;
}

int main() {
    std::string s1 = "ababcbacadefegdehijhklij";
    std::vector<int> result1 = partitionLabels(s1);
    for (int len : result1) {
        std::cout << len << " ";
    }
    std::cout << std::endl; // Output: 9 7 8

    std::string s2 = "eccbbbbdec";
    std::vector<int> result2 = partitionLabels(s2);
    for (int len : result2) {
        std::cout << len << " ";
    }
    std::cout << std::endl; // Output: 10

    return 0;
}

Complexity

• Time Complexity: O(N), where N is the length of the string. We iterate through the string twice (once to create the lastOccurrence map and once for partitioning).
• Space Complexity: O(1), because the lastOccurrence map will store at most 26 entries (for lowercase English letters). The space used by the result vector is proportional to the number of partitions, which is at most N in the worst case. However, in terms of Big O notation, it is considered constant space because the size of the alphabet is fixed.