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 HashMap to store the last occurrence index of each character in the string. This allows us to efficiently determine the rightmost boundary of a partition.

2. Partitioning:

   • Initialize start and end to 0. start tracks the beginning of the current partition, and end tracks the rightmost index reached so far within the current partition.
   • Iterate through the string:
     • For each character, update end to be the maximum of its last occurrence and the current end. This ensures end always points to the farthest rightmost index of any character encountered so far within the current partition.
     • If the current index equals end, it means all characters encountered within the current partition have been fully accounted for (their last occurrences are within the current partition). Add end - start + 1 (the length of the current partition) to the result list and update start to end + 1, starting a new partition.

Explanation

The core idea is to identify the boundaries of each partition by finding the rightmost occurrence of each character encountered. We greedily extend the current partition as far as possible until we're sure that all characters encountered within the partition will only appear within that partition. Once we've identified such a complete partition, we start a new one.

Code

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<Integer> partitionLabels(String s) {
        Map<Character, Integer> lastOccurrence = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            lastOccurrence.put(s.charAt(i), i);
        }

        List<Integer> partitionSizes = new ArrayList<>();
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, lastOccurrence.get(s.charAt(i)));
            if (i == end) {
                partitionSizes.add(end - start + 1);
                start = end + 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 lastOccurrence map and once to find the partitions).
• Space Complexity: O(1). The HashMap lastOccurrence stores at most 26 entries (for lowercase English letters), making its space usage constant. The partitionSizes list's size is also bounded by N, but we don't consider that in space complexity as it's directly related to the output size.