Domain 2MediumMEDIUM

Partition Labels

Partition a string into substrings where each character appears in at most one part by tracking the last occurrence of every character and greedily extending partition boundaries.

Domain: medium•Updated: 2026-08-31
#greedy#hash map#$O(N)$ time complexity#$O(1)$ space complexity

Problem Breakdown

We are given a string S consisting of lowercase English letters. The goal is to split this string into as many parts as possible such that each letter appears in at most one part across the entire partitioned set. We need to return an array representing the size (length) of these partitions.

Inputs:

  • A single string S containing characters 'a'-'z'. Length range [1, 500].

Outputs:

  • A list of integers where each integer represents the length of a valid partition substring.

Constraints & Edge Cases:

  • String length is small (up to 500), allowing O(N2)O(N^2) solutions theoretically, but an optimal approach should aim for linear time complexity (O(N)O(N)).
  • Characters are strictly lowercase English letters; no Unicode or special symbols need handling.
  • The input string will not be empty based on constraints (1 <= S.length), though the logic handles it gracefully.

Intuition

The core constraint is that if a character appears in one partition, all its occurrences must fall within that same partition. If we encounter a character at index i, and we know this character also exists later at index j > i, then our current partition cannot end before index j.

This suggests maintaining the rightmost boundary (end) of the current potential partition as we iterate through the string. For every character encountered, we update this boundary to be at least its last occurrence in the entire string. If our iterator reaches a point where it equals this calculated end, it implies that no characters from the start of the current segment appear beyond this index. Thus, a valid cut can occur here.

Approach

  1. Pre-compute Last Indices: First, iterate through the string once to build a hash map (last_occurrence) storing the highest (rightmost) index for each character in S. This allows O(1)O(1) lookup of where any specific character ends up later in the string.
  2. Greedy Expansion: Initialize two pointers: start marking the beginning of the current partition, and end tracking the furthest boundary required by characters seen so far within that partition. Iterate through the string with index i:
    • Update end = max(end, last_occurrence[S[i]]). This ensures we extend our window if a character in it appears later elsewhere.
  3. Identify Boundary: If the current iterator i equals end, all characters from start to i are self-contained within this range (none appear after i). We record the partition size (i - start + 1) and reset start = i + 1.
  4. Return Result: Collect sizes in a list and return it at the end of iteration.

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the length of string S. We iterate through the string twice: once to build the map (or implicitly during construction) and once for the greedy scan. Map operations are effectively constant time given a fixed alphabet size (Σ=26\Sigma = 26).
  • Space Complexity: O(1)O(1) or more precisely O(Σ)O(\Sigma), where Σ\Sigma is the character set size (lowercase English letters = 26). The dictionary stores at most 26 entries. This does not scale with input length N, making it constant space relative to string growth in terms of algorithmic complexity classes.

Solution

from typing import List

def partitionLabels(S: str) -> List[int]:
    # Step 1: Pre-compute the last occurrence index for every character in S
    # Iterating forward ensures later occurrences overwrite earlier ones, 
    # correctly storing the maximum (last) index.
    last_occurrence = {char: i for i, char in enumerate(S)}
    
    result = []
    start = end = 0
    
    # Step 2 & 3: Iterate through string to find partition boundaries greedily
    for i, char in enumerate(S):
        # Extend the current window's boundary if this character appears later elsewhere
        end = max(end, last_occurrence[char])
        
        # If we reached the furthest required index, a valid partition is complete
        if i == end:
            result.append(i - start + 1)
            start = i + 1
            
    return result

Edge Cases Handled

  • Single Character String: The loop runs once. i equals end. Partition size recorded as 1. Correct.
  • All Identical Characters (e.g., “aaaa”): Map stores last index at end of string. Loop extends end to the final ‘a’. Only cuts after the very last character, returning [N]. Correct.
  • Distinct Characters: Each char’s last occurrence is its own index. Partition size recorded immediately for each step (e.g., “abc” -> [1, 1, 1]). Correct.
  • Repeating Patterns at Boundaries: The max logic ensures that if a character appears in the next potential partition but was seen earlier, it forces the current partition to extend until its last occurrence is passed.