Partition Labels medium

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.

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]

Steps

1. Create a map: Create a map to store the last index of each character in the string. Iterate through the string, updating the map for each character.

2. Iterate and partition: Iterate through the string. For each character, keep track of the maximum last index seen so far (maxIndex).

3. Partition when maxIndex is reached: If the current index i is equal to maxIndex, it means all characters up to this point belong to the same partition. Add the partition size (maxIndex - partitionStart + 1) to the result list and update partitionStart to maxIndex + 1.

Explanation

The key idea is to find the rightmost occurrence of each character. A partition can only end when we've reached the rightmost occurrence of all characters encountered so far. The maxIndex variable keeps track of this rightmost occurrence. When the current index reaches maxIndex, we know we've included all the rightmost occurrences of characters encountered so far, hence we can create a partition at that point.

Code

function partitionLabels(s: string): number[] {
    const lastIndexMap: Map<string, number> = new Map();

    // Store the last index of each character
    for (let i = 0; i < s.length; i++) {
        lastIndexMap.set(s[i], i);
    }

    const result: number[] = [];
    let partitionStart = 0;
    let maxIndex = 0;

    for (let i = 0; i < s.length; i++) {
        maxIndex = Math.max(maxIndex, lastIndexMap.get(s[i])!); //Get last index and handle potential undefined using ! (assuming input is valid)

        if (i === maxIndex) {
            result.push(maxIndex - partitionStart + 1);
            partitionStart = maxIndex + 1;
        }
    }

    return result;
};

Complexity

• Time Complexity: O(n), where n is the length of the string. We iterate through the string twice: once to build the map and once to create partitions.
• Space Complexity: O(1), assuming the number of unique characters in the string is constant (or at most a small constant related to the alphabet size). The map's space usage is bounded. If we consider that the number of unique characters can be proportional to n, the space complexity would become O(n) in the worst case.