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 whose concatenation equals the input string.

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 Mapping: Create a dictionary (hash map) to store the last occurrence index of each character in the string. Iterate through the string, updating the dictionary for each character.

2. Partitioning:

   • Initialize last_index to track the maximum last occurrence index seen so far.
   • Initialize start_index to 0, marking the beginning of the current partition.
   • Iterate through the string:
     • For each character, update last_index if its last occurrence index is greater.
     • If the current index equals last_index, it means all characters up to this point belong to the same partition. Add the partition size (last_index - start_index + 1) to the result list.
     • Update start_index to the next index, beginning a new partition.

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

Explanation

The key idea is to find the last occurrence of each character. A partition can only end when we reach a point where all characters encountered so far have their last occurrences within the current partition. This is precisely when the current index matches the maximum last occurrence index encountered so far (last_index).

Code

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public IList<int> PartitionLabels(string s) {
        Dictionary<char, int> lastOccurrences = new Dictionary<char, int>();
        for (int i = 0; i < s.Length; i++) {
            lastOccurrences[s[i]] = i;
        }

        List<int> partitionSizes = new List<int>();
        int startIndex = 0;
        int lastIndex = 0;

        for (int i = 0; i < s.Length; i++) {
            lastIndex = Math.Max(lastIndex, lastOccurrences[s[i]]);
            if (i == lastIndex) {
                partitionSizes.Add(lastIndex - startIndex + 1);
                startIndex = lastIndex + 1;
            }
        }

        return partitionSizes;
    }
}

Complexity

• Time Complexity: O(N), where N is the length of the string. We iterate through the string twice (once to build the lastOccurrences dictionary and once to find the partitions).
• Space Complexity: O(1), because the size of the lastOccurrences dictionary is at most 26 (for lowercase English letters). The space used by the partitionSizes list is proportional to the number of partitions, which is at most N in the worst case (all characters are unique). Therefore, space complexity is considered O(1) in terms of input string size.